Submission #682653

#TimeUsernameProblemLanguageResultExecution timeMemory
682653benson1029Examination (JOI19_examination)C++14
100 / 100
559 ms108336 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() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> q;
	for(int i=0; i<n; i++) {
		cin >> 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++) cout << ans[i] << "\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...