Submission #682656

#TimeUsernameProblemLanguageResultExecution timeMemory
682656benson1029Examination (JOI19_examination)C++14
100 / 100
662 ms103368 KiB
#include<bits/stdc++.h> using namespace std; struct entry{ int op; int a,b,c; int id; }; bool cmpa(entry x, entry y) { if(x.a == y.a) return x.op < y.op; return x.a > y.a; } bool cmpb(entry x, entry y) { if(x.b == y.b) return x.op < y.op; return x.b > y.b; } struct node{ int v; node *l, *r; node(): v(0), l(NULL), r(NULL) {} }; entry a[200005]; entry b[200005]; int ans[200005]; pair<int,int> c[200005]; int n,q; int w,x,y; void upd(node *x, long long l, long long r, int pos) { if(l == r) { x->v++; } else { if(x->l == NULL) { x -> l = new node(); x -> r = new node(); } if(pos<=(l+r)/2) upd(x->l, l, (l+r)/2, pos); else upd(x->r, (l+r)/2+1, r, pos); x->v = x->l->v + x->r->v; } } int qry(node *x, long long l, long long r, int ll, int rr) { if(ll > r || rr < l) return 0; if(ll <= l && r <= rr) return x -> v; if(x -> l == NULL) return x -> v; return qry(x->l, l, (l+r)/2, ll, rr) + qry(x->r, (l+r)/2+1, r, ll, rr); } void cdq(int l, int r) { if(l >= r) return; int mid = (l+r)/2; int ptr = 0; for(int i=l; i<=r; i++) { if(i <= mid && a[i].op == 1) { b[ptr] = a[i]; c[ptr] = make_pair(a[i].c,ptr); ptr++; } else if(i > mid && a[i].op == 2) { b[ptr] = a[i]; c[ptr] = make_pair(a[i].c,ptr); ptr++; } } sort(c,c+ptr); int temp = 0; for(int i=0; i<ptr; i++) { if(i>0 && c[i].first != c[i-1].first) temp++; b[c[i].second].c = temp; } sort(b,b+ptr,cmpb); node *rt = new node(); for(int i=0; i<ptr; i++) { if(b[i].op == 1) { upd(rt, 0, r-l+1, b[i].c); } else { ans[b[i].id] += qry(rt, 0, r-l+1, b[i].c, r-l+1); } } cdq(l, mid); cdq(mid+1, r); } int main() { scanf("%d%d", &n, &q); for(int i=0; i<n; i++) { scanf("%d%d", &x, &y); a[i] = (entry){1,x,y,x+y,0}; } for(int i=n; i<n+q; i++) { cin >> w >> x >> y; a[i] = (entry){2,w,x,y,i-n}; } sort(a,a+n+q,cmpa); cdq(0,n+q-1); for(int i=0; i<q; i++) printf("%d\n", ans[i]); }

Compilation message (stderr)

examination.cpp: In function 'int main()':
examination.cpp:80:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |  scanf("%d%d", &n, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~
examination.cpp:82:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |   scanf("%d%d", &x, &y);
      |   ~~~~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...