fork download
copy 
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <cassert>
  4. #include <cstdlib>
  5. #include <cstring>
  6. #include <cstdio>
  7. #include <cmath>
  8. #include <queue>
  9. #include <map>
  10. #include <set>
  11.  
  12. using namespace std;
  13.  
  14. #define type(x) __typeof((x).begin())
  15. #define foreach(i, x) for(type(x) i = (x).begin(); i != (x).end(); i++)
  16.  
  17. typedef long long ll;
  18. typedef pair < int, int > ii;
  19.  
  20. const int inf = 1e9 + 333;
  21. const ll linf = 1e18 + 333;
  22.  
  23. const int N = 1e5 + 5;
  24. const int LOG = 18;
  25.  
  26. int n, m, b[N], t[LOG][N], last[N << 2], avl[N << 2];
  27. ii a[N];
  28.  
  29. void init(int x, int l, int r, int dep = 0) {
  30.     if(l == r) {
  31.         t[dep][l] = a[l].first;
  32.         return;
  33.     }
  34.     int m = l + r >> 1;
  35.     init(x + x, l, m, dep + 1);
  36.     init(x + x + 1, m + 1, r, dep + 1);
  37.     merge(t[dep + 1] + l, t[dep + 1] + m + 1, t[dep + 1] + m + 1, t[dep + 1] + r + 1, t[dep] + l);
  38. }
  39.  
  40. void doit(int x, int l, int r, int a, int b, int dep) {
  41.     if(b > a) {
  42.         avl[x] += upper_bound(t[dep] + l, t[dep] + r + 1, b) - upper_bound(t[dep] + l, t[dep] + r + 1, a);
  43.         last[x] = b;
  44.     }
  45. }
  46.  
  47. void push(int x, int l, int r, int dep) {
  48.     int m = l + r >> 1;
  49.     doit(x + x, l, m, last[x + x], last[x], dep + 1);
  50.     doit(x + x + 1, m + 1, r, last[x + x + 1], last[x], dep + 1);
  51. }
  52.  
  53. int query_update(int x, int l, int r, int x1, int x2, int k, int rem, int dep = 0) {
  54.  
  55.     doit(x, l, r, last[x], k, dep);
  56.     push(x, l, r, dep);
  57.  
  58.     if(x2 < l or r < x1)
  59.         return 0;
  60.  
  61.     if(x1 <= l and r <= x2 and avl[x] <= rem) {
  62.         int res = avl[x];
  63.         avl[x] = 0;
  64.         return res;
  65.     }
  66.  
  67.     int m = l + r >> 1;
  68.  
  69.     int res = query_update(x + x, l, m, x1, x2, k, rem, dep + 1);
  70.  
  71.     assert(res <= rem);
  72.  
  73.     if(res == rem) {
  74.         avl[x] = avl[x + x] + avl[x + x + 1];
  75.         return res;
  76.     }
  77.  
  78.     res += query_update(x + x + 1, m + 1, r, x1, x2, k, rem - res, dep + 1);
  79.  
  80.     avl[x] = avl[x + x] + avl[x + x + 1];
  81.  
  82.     return res;
  83.  
  84. }
  85.  
  86. int main () {
  87.  
  88.     scanf("%d", &n);
  89.  
  90.     for(int i = 1; i <= n; i++)
  91.         scanf("%d %d", &a[i].second, &a[i].first);
  92.  
  93.     sort(a + 1, a + n + 1);
  94.  
  95.     for(int i = 1; i <= n; i++)
  96.         swap(a[i].first, a[i].second);
  97.  
  98.     init(1, 1, n);
  99.  
  100.     scanf("%d", &m);
  101.  
  102.     for(int i = 1; i <= m; i++)
  103.         scanf("%d", b + i);
  104.  
  105.     sort(b + 1, b + m + 1);
  106.  
  107.     for(int i = 1; i <= n; i++)
  108.         printf("%d %d\n", a[i].first, a[i].second);
  109.  
  110.     int j = 1;
  111.  
  112.     for(int i = 1; i <= m; i++) {
  113.         while(j <= n and a[j].second < b[i])
  114.             j++;
  115.         if(j > n) {
  116.             puts("FAIL");
  117.             return 0;
  118.         }
  119.         int ans = query_update(1, 1, n, j, n, b[i], b[i]);
  120.         printf("j = %d ans = %d\n", j, ans);
  121.         if(ans < b[i]) {
  122.             printf("FAIL --> b[%d] = %d", i, b[i]);
  123.             return 0;
  124.         }
  125.     }
  126.  
  127.     puts("OK");
  128.  
  129.     return 0;
  130.  
  131. }
  132.  
Runtime error #stdin #stdout 0s 22536KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/IetuGM
language:
C++ (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!