Submission #682656

#	Time	Username	Problem	Language	Result	Execution time	Memory
682656		benson1029	Examination (JOI19_examination)	C++14	100 / 100	662 ms	103368 KiB

examination

#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);
      |   ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 2 / 2
• Subtask 2: 20 / 20
• Subtask 3: 21 / 21
• Subtask 4: 57 / 57