oj.uz

답안 #172329

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
172329 2020-01-01T09:23:51 Z dennisstar Examination (JOI19_examination) C++11
100 / 100
 2186 ms 207092 KB 
#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

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.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 380 KB Output is correct
7 Correct 29 ms 7032 KB Output is correct
8 Correct 30 ms 7032 KB Output is correct
9 Correct 30 ms 7004 KB Output is correct
10 Correct 20 ms 3960 KB Output is correct
11 Correct 23 ms 5880 KB Output is correct
12 Correct 12 ms 760 KB Output is correct
13 Correct 30 ms 6904 KB Output is correct
14 Correct 30 ms 6904 KB Output is correct
15 Correct 31 ms 7032 KB Output is correct
16 Correct 19 ms 5784 KB Output is correct
17 Correct 9 ms 1272 KB Output is correct
18 Correct 5 ms 632 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2049 ms 197584 KB Output is correct
2 Correct 2178 ms 197668 KB Output is correct
3 Correct 2094 ms 197560 KB Output is correct
4 Correct 910 ms 104296 KB Output is correct
5 Correct 741 ms 127044 KB Output is correct
6 Correct 337 ms 8716 KB Output is correct
7 Correct 1867 ms 197736 KB Output is correct
8 Correct 1832 ms 197548 KB Output is correct
9 Correct 1615 ms 197532 KB Output is correct
10 Correct 529 ms 116080 KB Output is correct
11 Correct 245 ms 20984 KB Output is correct
12 Correct 94 ms 8296 KB Output is correct

Subtask #3
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2049 ms 197584 KB Output is correct
2 Correct 2178 ms 197668 KB Output is correct
3 Correct 2094 ms 197560 KB Output is correct
4 Correct 910 ms 104296 KB Output is correct
5 Correct 741 ms 127044 KB Output is correct
6 Correct 337 ms 8716 KB Output is correct
7 Correct 1867 ms 197736 KB Output is correct
8 Correct 1832 ms 197548 KB Output is correct
9 Correct 1615 ms 197532 KB Output is correct
10 Correct 529 ms 116080 KB Output is correct
11 Correct 245 ms 20984 KB Output is correct
12 Correct 94 ms 8296 KB Output is correct
13 Correct 1789 ms 198092 KB Output is correct
14 Correct 2186 ms 197768 KB Output is correct
15 Correct 2071 ms 197528 KB Output is correct
16 Correct 774 ms 104628 KB Output is correct
17 Correct 713 ms 127592 KB Output is correct
18 Correct 348 ms 8652 KB Output is correct
19 Correct 1768 ms 197840 KB Output is correct
20 Correct 1944 ms 198112 KB Output is correct
21 Correct 1605 ms 197980 KB Output is correct
22 Correct 537 ms 116456 KB Output is correct
23 Correct 245 ms 21024 KB Output is correct
24 Correct 95 ms 8296 KB Output is correct

Subtask #4
57.0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 380 KB Output is correct
7 Correct 29 ms 7032 KB Output is correct
8 Correct 30 ms 7032 KB Output is correct
9 Correct 30 ms 7004 KB Output is correct
10 Correct 20 ms 3960 KB Output is correct
11 Correct 23 ms 5880 KB Output is correct
12 Correct 12 ms 760 KB Output is correct
13 Correct 30 ms 6904 KB Output is correct
14 Correct 30 ms 6904 KB Output is correct
15 Correct 31 ms 7032 KB Output is correct
16 Correct 19 ms 5784 KB Output is correct
17 Correct 9 ms 1272 KB Output is correct
18 Correct 5 ms 632 KB Output is correct
19 Correct 2049 ms 197584 KB Output is correct
20 Correct 2178 ms 197668 KB Output is correct
21 Correct 2094 ms 197560 KB Output is correct
22 Correct 910 ms 104296 KB Output is correct
23 Correct 741 ms 127044 KB Output is correct
24 Correct 337 ms 8716 KB Output is correct
25 Correct 1867 ms 197736 KB Output is correct
26 Correct 1832 ms 197548 KB Output is correct
27 Correct 1615 ms 197532 KB Output is correct
28 Correct 529 ms 116080 KB Output is correct
29 Correct 245 ms 20984 KB Output is correct
30 Correct 94 ms 8296 KB Output is correct
31 Correct 1789 ms 198092 KB Output is correct
32 Correct 2186 ms 197768 KB Output is correct
33 Correct 2071 ms 197528 KB Output is correct
34 Correct 774 ms 104628 KB Output is correct
35 Correct 713 ms 127592 KB Output is correct
36 Correct 348 ms 8652 KB Output is correct
37 Correct 1768 ms 197840 KB Output is correct
38 Correct 1944 ms 198112 KB Output is correct
39 Correct 1605 ms 197980 KB Output is correct
40 Correct 537 ms 116456 KB Output is correct
41 Correct 245 ms 21024 KB Output is correct
42 Correct 95 ms 8296 KB Output is correct
43 Correct 1718 ms 206980 KB Output is correct
44 Correct 1737 ms 206976 KB Output is correct
45 Correct 1903 ms 207092 KB Output is correct
46 Correct 790 ms 118644 KB Output is correct
47 Correct 802 ms 182296 KB Output is correct
48 Correct 310 ms 8616 KB Output is correct
49 Correct 1684 ms 206744 KB Output is correct
50 Correct 1464 ms 206876 KB Output is correct
51 Correct 1434 ms 206736 KB Output is correct
52 Correct 675 ms 179812 KB Output is correct
53 Correct 272 ms 28696 KB Output is correct