Morass

RAIN-SONGMAN

Sep 9th, 2016
203
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.34 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. using LINT = long long int;
  5. using PII = pair<int,int>;
  6.  
  7. #define PB push_back
  8. #define FI first
  9. #define SE second
  10. #define REP(i,n) for(int i=0;i<(n);++i)
  11. #define FOR(i, a, b) for(int i=(a);i<(b);++i)
  12.  
  13.  
  14. struct SegmentTree {
  15.     int treelen;
  16.     int * tree;
  17.     bool * dirty;
  18.  
  19.     SegmentTree(int len) {
  20.         treelen = 1;
  21.         while(treelen < len) treelen *= 2;
  22.         tree = new int[2*treelen];
  23.         dirty = new bool[2*treelen];
  24.         memset(tree, 0, 2*treelen*sizeof(int));
  25.         memset(dirty, 0, 2*treelen*sizeof(bool));
  26.     }
  27.  
  28.     //modify
  29.     int defval() { return 0; }
  30.     int queryval(int a, int b) { return max(a,b); }
  31.  
  32.     int query(int l, int r) {
  33.         return seg_query(l, r, 0, treelen - 1, 0);
  34.     }
  35.  
  36.  
  37.     void prop_node(int node) {
  38.         dirty[node] = false;
  39.         tree[2*node+1] += tree[node];
  40.         tree[2*node+2] += tree[node];
  41.         tree[node]=0;
  42.         dirty[2*node+1] = true;
  43.         dirty[2*node+2] = true;
  44.     }
  45.  
  46.     int seg_query(int l, int r, int ll, int rr, int node) {
  47.         if(l>r) return defval();
  48.  
  49.         if(l <= ll && rr <= r) return tree[node];
  50.  
  51.         if(dirty[node]) prop_node(node);
  52.  
  53.         int mid = (ll + rr) / 2;
  54.  
  55.         int r1 = seg_query(l, min(r, mid), ll, mid, 2*node + 1);
  56.         int r2 = seg_query(max(mid+1, l), r, mid+1, rr, 2*node + 2);
  57.  
  58.         return queryval(r1, r2);
  59.     }
  60.  
  61.     void insert(int l, int r, int val) {
  62.         seg_insert(l, r, 0, treelen - 1, 0, val);
  63.     }
  64.  
  65.     void seg_insert(int l, int r, int ll, int rr, int node, int val) {
  66.         if(l>r) return;
  67.  
  68.         if(l <= ll && rr <= r) {
  69.             tree[node] += val;
  70.             if(ll != rr)
  71.                 dirty[node] = true;
  72.             return;
  73.         }
  74.  
  75.         if(dirty[node]) prop_node(node);
  76.  
  77.         int mid = (ll + rr) / 2;
  78.  
  79.         seg_insert(l, min(r, mid), ll, mid, 2*node + 1, val);
  80.         seg_insert(max(mid+1, l), r, mid+1, rr, 2*node + 2, val);
  81.  
  82.         // tree[node] = queryval(tree[2*node+1], tree[2*node+2]);
  83.     }
  84. };
  85.  
  86. int main() {
  87.     SegmentTree tree(1000007);
  88.     int N,M,L;
  89.     cin>>N>>M>>L;
  90.     REP(i,N){
  91.         int l,r;
  92.         cin>>l>>r;
  93.         tree.insert(l,r,1);
  94.     }
  95.     REP(i,M){
  96.         int a;
  97.         cin>>a;
  98.         cout<<tree.query(a,a)<<endl;
  99.     }
  100.  
  101.     return 0;
  102. }
Advertisement
Add Comment
Please, Sign In to add comment