Guest User

Untitled

a guest
Aug 16th, 2015
171
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #include <assert.h>
  3. #include <unordered_map>
  4. using namespace std;
  5.  
  6. typedef long long ll;
  7. typedef long double ld;
  8. typedef vector < long long > vll;
  9. typedef pair < long long, long long > pll;
  10. typedef pair < int, int > pii;
  11. typedef vector < int > vii;
  12.  
  13. #define csl ios_base::sync_with_stdio(false); cin.tie(NULL)
  14. #define l(x) (((x) << 1) | 1)
  15. #define r(x) ((l(x)) + 1)
  16. #define mp make_pair
  17. #define fst first
  18. #define snd second
  19.  
  20. ll t, n, u, v, m, q, r, ql, qr, k, l, s, x, y, w, a, b;
  21. const int N = 1e6 + 5;
  22. const long long mod = 1e9 + 7;
  23. const long long INF = 1LL << 57LL;
  24. const bool JUDGE = false;
  25. int X[60000], Y[60000];
  26. pii S[N], W[N], _S[N], _W[N];
  27. bool valid[N];
  28. priority_queue < pii > wq, sq;
  29. bool p(ll tim) {
  30.     int x = 0;
  31.     int i = 0;
  32.     wq = priority_queue < pii > ();
  33.     sq = priority_queue < pii > ();
  34.     for (int i = 0; i < n; ++i) valid[i] = true;
  35.     while (i < a) {
  36.         while (x < n && W[x].fst < X[i]) {
  37.             if (valid[W[x].snd]) {
  38.                 valid[W[x].snd] = false;
  39.                 wq.push(_S[W[x].snd]);
  40.             }
  41.             x++;
  42.         }
  43.         int j = 0;
  44.         while (wq.size() > 0 && j < tim) {
  45.             pii y = wq.top();
  46.             wq.pop();
  47.             j++;
  48.         }
  49.         i++;
  50.     }
  51.     while (wq.size() > 0) {
  52.         pii y = wq.top();
  53.         wq.pop();
  54.         valid[y.snd] = true;
  55.     }
  56.     i = 0;
  57.     x = 0;
  58.     while (i < b) {
  59.         while (x < n && S[x].fst < Y[i]) {
  60.             if (valid[S[x].snd]) {
  61.                 sq.push(_W[S[x].snd]);
  62.                 valid[S[x].snd] = false;
  63.             }
  64.             x++;
  65.         }
  66.         int j = 0;
  67.         while (sq.size() > 0 && (j < tim)) {
  68.             pii y = sq.top();
  69.             sq.pop();
  70.             valid[y.snd] = false;
  71.             j++;
  72.         }
  73.         i++;
  74.     }
  75.     while (sq.size() > 0) {
  76.         pii y = sq.top();
  77.         sq.pop();
  78.         valid[y.snd] = true;
  79.     }
  80.     for (int i = 0; i < n; ++i) if (valid[i]) {
  81.         //cout << i << "h\n";
  82.         return false;
  83.     }
  84.     return true;
  85. }
  86. int main(){
  87.     csl;
  88.     if (JUDGE) {
  89.         freopen("in.txt", "r", stdin);
  90.         freopen("out.txt", "w", stdout);
  91.     }
  92.     cin >> a >> b >> n;
  93.     for (int i = 0; i < a; ++i) {
  94.         cin >> X[i];
  95.     }
  96.     for (int i = 0; i < b; ++i) {
  97.         cin >> Y[i];
  98.     }
  99.     for (int i = 0; i < n; ++i) {
  100.         cin >> W[i].fst >> S[i].fst;
  101.         W[i].snd = S[i].snd = i;
  102.         _S[i] = S[i];
  103.         _W[i] = W[i];
  104.     }
  105.     ll lo = 1, hi = a + b + n;
  106.     sort(W, W + n), sort(S, S + n);
  107.     sort(X, X + a), sort(Y, Y + b);
  108.     while (lo < hi) {
  109.         int mid = lo + (hi - lo) / 2;
  110.         if (p(mid)) hi = mid;
  111.         else lo = mid + 1;
  112.     }
  113.     if (p(lo))  cout << lo << '\n';
  114.     else cout << -1 << '\n';
  115.     return 0;
  116. }
RAW Paste Data