This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |