Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- using LINT = long long int;
- using PII = pair<int,int>;
- #define PB push_back
- #define FI first
- #define SE second
- #define REP(i,n) for(int i=0;i<(n);++i)
- #define FOR(i, a, b) for(int i=(a);i<(b);++i)
- struct SegmentTree {
- int treelen;
- int * tree;
- bool * dirty;
- SegmentTree(int len) {
- treelen = 1;
- while(treelen < len) treelen *= 2;
- tree = new int[2*treelen];
- dirty = new bool[2*treelen];
- memset(tree, 0, 2*treelen*sizeof(int));
- memset(dirty, 0, 2*treelen*sizeof(bool));
- }
- //modify
- int defval() { return 0; }
- int queryval(int a, int b) { return max(a,b); }
- int query(int l, int r) {
- return seg_query(l, r, 0, treelen - 1, 0);
- }
- void prop_node(int node) {
- dirty[node] = false;
- tree[2*node+1] += tree[node];
- tree[2*node+2] += tree[node];
- tree[node]=0;
- dirty[2*node+1] = true;
- dirty[2*node+2] = true;
- }
- int seg_query(int l, int r, int ll, int rr, int node) {
- if(l>r) return defval();
- if(l <= ll && rr <= r) return tree[node];
- if(dirty[node]) prop_node(node);
- int mid = (ll + rr) / 2;
- int r1 = seg_query(l, min(r, mid), ll, mid, 2*node + 1);
- int r2 = seg_query(max(mid+1, l), r, mid+1, rr, 2*node + 2);
- return queryval(r1, r2);
- }
- void insert(int l, int r, int val) {
- seg_insert(l, r, 0, treelen - 1, 0, val);
- }
- void seg_insert(int l, int r, int ll, int rr, int node, int val) {
- if(l>r) return;
- if(l <= ll && rr <= r) {
- tree[node] += val;
- if(ll != rr)
- dirty[node] = true;
- return;
- }
- if(dirty[node]) prop_node(node);
- int mid = (ll + rr) / 2;
- seg_insert(l, min(r, mid), ll, mid, 2*node + 1, val);
- seg_insert(max(mid+1, l), r, mid+1, rr, 2*node + 2, val);
- // tree[node] = queryval(tree[2*node+1], tree[2*node+2]);
- }
- };
- int main() {
- SegmentTree tree(1000007);
- int N,M,L;
- cin>>N>>M>>L;
- REP(i,N){
- int l,r;
- cin>>l>>r;
- tree.insert(l,r,1);
- }
- REP(i,M){
- int a;
- cin>>a;
- cout<<tree.query(a,a)<<endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment