Submission #172329

#	Time	Username	Problem	Language	Result	Execution time	Memory
172329		dennisstar	Examination (JOI19_examination)	C++11	100 / 100	2186 ms	207092 KiB

examination

#include <bits/stdc++.h>
#define fi first
#define se second
#define ryan bear
#define all(V) ((V).begin()), ((V).end())
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
typedef vector<int> vim;
typedef vector<ll> vlm;
 
int R, C;
struct dty {
	dty *l, *r;
	int dt, L, R; int Key;
	int md;
	dty(int k) {Key=k; dt=0; l=r=NULL;}
	inline void upd(int y, int val, int ys, int ye) {
		md=(ys+ye)/2;
		if (Key) {
			if (Key==y) {dt+=val; return ;}
			if (Key<=md) { l=new dty(Key); l->dt=dt; }
			else { r=new dty(Key); r->dt=dt; }
			Key=0;
		}
		if (y<=md) {
			if (!l) l=new dty(y);
			l->upd(y, val, ys, md);
		}
		else {
			if (!r) r=new dty(y);
			r->upd(y, val, md+1, ye);
		}
		L=(l?l->dt:0);
		R=(r?r->dt:0);
		dt=L+R;
	}
	inline int get(int y1, int y2, int ys, int ye) {
		md=(ys+ye)/2;
		if (Key) return (y1<=Key&&Key<=y2)?dt:0;
		if (y1<=ys&&ye<=y2) return dt;
		L=R=0;
		if (!(md<y1)) L=(l?(l->get(y1, y2, ys, md)):0);
		if (md+1<=y2&&md+1<=ye) R=(r?r->get(y1, y2, md+1, ye):0);
		return L+R;
	}
};

struct dtx {
	dty *seg;
	dtx *l, *r;
	int md;
	int L, R;
	dtx() {l=r=NULL; seg=NULL;}
	inline void upd(int x, int y, int val, int xs, int xe) {
		if (!seg) seg=new dty(y);
		if (xs==xe) {seg->upd(y, val, 1, C); return ;}
		md=(xs+xe)/2;
		if (x<=md) {
			if (!l) l=new dtx();
			l->upd(x, y, val, xs, md);
		}
		else {
			if (!r) r=new dtx();
			r->upd(x, y, val, md+1, xe);
		}
		seg->upd(y, val, 1, C);
	}
	inline int get(int x1, int y1, int x2, int y2, int xs, int xe) {
		if (!seg) return 0;
		if (x1<=xs&&xe<=x2) return seg->get(y1, y2, 1, C);
		md=(xs+xe)/2;
		L=R=0;
		if (x1<=md) L=(l?(l->get(x1, y1, x2, y2, xs, md)):0);
		if (md+1<=x2&&md+1<=xe) R=(r?(r->get(x1, y1, x2, y2, md+1, xe)):0);
		return L+R;
	}
};

dtx *root=new dtx();

struct Query {
	int x, y, z, n, ans;
};

vim cp1, cp2, cp3;
int N, Q;
int S[100010], T[100010], ST[100010], X[100010], Y[100010], Z[100010];
Query Qu[100010]; pair<int, pii> ar[100010];


int main() {
	R=C=100005;
	scanf("%d %d", &N, &Q);
	for (int i=1; i<=N; i++) {
		scanf("%d %d", &S[i], &T[i]);
		cp1.push_back(S[i]); cp2.push_back(T[i]); cp3.push_back(S[i]+T[i]);
		ST[i]=S[i]+T[i];
	}
	sort(all(cp1)); cp1.erase(unique(all(cp1)), cp1.end());
	sort(all(cp2)); cp2.erase(unique(all(cp2)), cp2.end());
	sort(all(cp3)); cp3.erase(unique(all(cp3)), cp3.end());
	for (int i=1; i<=N; i++) {
		S[i]=lower_bound(all(cp1), S[i])-cp1.begin()+1;
		T[i]=lower_bound(all(cp2), T[i])-cp2.begin()+1;
		ST[i]=lower_bound(all(cp3), ST[i])-cp3.begin()+1;
		ar[i-1]={ST[i], make_pair(S[i], T[i])};
	}
	sort(ar, ar+N, [](pair<int, pii> x1, pair<int, pii> x2){return x1.fi>x2.fi;});
	for (int i=1; i<=Q; i++) {
		scanf("%d %d %d", &X[i], &Y[i], &Z[i]);
		X[i]=lower_bound(all(cp1), X[i])-cp1.begin()+1;
		Y[i]=lower_bound(all(cp2), Y[i])-cp2.begin()+1;
		Z[i]=lower_bound(all(cp3), Z[i])-cp3.begin()+1;
		Qu[i-1]={Z[i], X[i], Y[i], i, 0};
	}
	sort(Qu, Qu+Q, [](Query x1, Query x2){return x1.x>x2.x;});
	for (int i=0, j=0; i<Q; i++) {
		for (; j<N&&ar[j].fi>=Qu[i].x; j++) root->upd(ar[j].se.fi, ar[j].se.se, 1, 1, R);
		Qu[i].ans=root->get(Qu[i].y, Qu[i].z, R, C, 1, R);
	}
	sort(Qu, Qu+Q, [](Query x1, Query x2){return x1.n<x2.n;});
	for (int i=0; i<Q; i++) printf("%d\n", Qu[i].ans);
	return 0;
}

Compilation message (stderr)

examination.cpp: In function 'int main()':
examination.cpp:96:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &N, &Q);
  ~~~~~^~~~~~~~~~~~~~~~~
examination.cpp:98:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &S[i], &T[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:113:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &X[i], &Y[i], &Z[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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