답안 #471430

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
471430	2021-09-09T07:09:13 Z	CSQ31	무지개나라 (APIO17_rainbow)	C++17	100 / 100	1201 ms	124744 KB

rainbow

#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
int r,c;
#define fi first
#define se second
#define all(a) a.begin(),a.end()
#define pb push_back
typedef pair<int,int> pii;
const int MAXN = 2e5;
struct fen{
	vector<vector<int>>bit;
	vector<set<int>>data;
	int r,c;
	fen(){}
	fen(int _r,int _c){
		r = _r;
		c = _c;
		bit.resize(r+1);
		data.resize(r+1);
	}
	
	void add(int x,int y){
		data[x].insert(y);
	}
	int query(int x,int l,int r){
		int res = 0;
		for(int i=x;i;i-=i&(-i)){
			int p = lower_bound(all(bit[i]),l) - bit[i].begin();
			int q = upper_bound(all(bit[i]),r) - bit[i].begin();
			res+=q-p;
		}
		return res;
	}
	int query(int xl,int xr,int yl,int yr){
		if(xl > xr)return 0;
		return query(xr,yl,yr) - query(xl-1,yl,yr);
	}
	
	void build(){
		for(int i=1;i<=r;i++){
			for(int j=i;j<=r;j+=j&(-j)){
				for(int x:data[i])bit[j].pb(x);
			}
		}
		for(int i=1;i<=r;i++)sort(all(bit[i]));
	}
}river,hedge,vedge,vert;
pii mx = {-1e9,-1e9};
pii mn = {1e9,1e9};
void init(int R, int C, int sr, int sc, int M, char *S) {
	r = R;
	c = C;
	river = fen(r,c);
	hedge = fen(r+1,c);
	vedge = fen(r,c+1);
	vert = fen(r+1,c+1);
int x = sr;
	int y = sc;
	river.add(x,y);
	hedge.add(x,y);
	hedge.add(x+1,y);
	vedge.add(x,y);
	vedge.add(x,y+1);
	vert.add(x,y);
	vert.add(x+1,y);
	vert.add(x,y+1);
	vert.add(x+1,y+1);
	mx.fi = max(mx.fi,x);
	mx.se = max(mx.se,y);
	mn.fi = min(mn.fi,x);
	mn.se = min(mn.se,y);
	for(int i=0;i<M;i++){
		char c = S[i];
		if(c =='N')x--;
		if(c =='S')x++;
		if(c =='W')y--;
		if(c =='E')y++;
		river.add(x,y);
		hedge.add(x,y);
		hedge.add(x+1,y);
		vedge.add(x,y);
		vedge.add(x,y+1);
		vert.add(x,y);
		vert.add(x+1,y);
		vert.add(x,y+1);
		vert.add(x+1,y+1);
		mx.fi = max(mx.fi,x);
		mx.se = max(mx.se,y);
		mn.fi = min(mn.fi,x);
		mn.se = min(mn.se,y);
	}
	river.build();
	vert.build();
	hedge.build();
	vedge.build();
}

int colour(int ar, int ac, int br, int bc) {
	int C = (!(mn.fi <= ar || mn.se <= ac || mx.fi >= br || mx.se >= bc)) + 1;
	int A = river.query(ar,br,ac,bc);
	int V = vert.query(ar+1,br,ac+1,bc);
	int E = hedge.query(ar+1,br,ac,bc) + vedge.query(ar,br,ac+1,bc);
	//cout<<E<<" "<<V<<" "<<A<<" "<<C<<'\n';
	int F = 1+C+E-V;
    return F - A - 1;
}

Subtask #1
11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	332 KB	Output is correct
2	Correct	4 ms	588 KB	Output is correct
3	Correct	2 ms	332 KB	Output is correct
4	Correct	3 ms	332 KB	Output is correct
5	Correct	5 ms	588 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	0 ms	204 KB	Output is correct
10	Correct	0 ms	204 KB	Output is correct
11	Correct	3 ms	332 KB	Output is correct
12	Correct	4 ms	460 KB	Output is correct
13	Correct	6 ms	716 KB	Output is correct
14	Correct	6 ms	844 KB	Output is correct
15	Correct	0 ms	204 KB	Output is correct
16	Correct	0 ms	204 KB	Output is correct
17	Correct	1 ms	204 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	283 ms	20012 KB	Output is correct
4	Correct	419 ms	33084 KB	Output is correct
5	Correct	447 ms	32728 KB	Output is correct
6	Correct	434 ms	25664 KB	Output is correct
7	Correct	433 ms	25376 KB	Output is correct
8	Correct	67 ms	1020 KB	Output is correct
9	Correct	428 ms	33028 KB	Output is correct
10	Correct	452 ms	32824 KB	Output is correct
11	Correct	437 ms	25772 KB	Output is correct
12	Correct	348 ms	30568 KB	Output is correct
13	Correct	346 ms	33064 KB	Output is correct
14	Correct	364 ms	32788 KB	Output is correct
15	Correct	377 ms	25916 KB	Output is correct
16	Correct	323 ms	23924 KB	Output is correct

Subtask #3
24.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	908 ms	108400 KB	Output is correct
3	Correct	279 ms	115252 KB	Output is correct
4	Correct	311 ms	115492 KB	Output is correct
5	Correct	337 ms	99412 KB	Output is correct
6	Correct	165 ms	67248 KB	Output is correct
7	Correct	251 ms	75320 KB	Output is correct
8	Correct	272 ms	29792 KB	Output is correct
9	Correct	267 ms	27704 KB	Output is correct
10	Correct	107 ms	35700 KB	Output is correct
11	Correct	179 ms	46528 KB	Output is correct
12	Correct	941 ms	108384 KB	Output is correct
13	Correct	276 ms	115300 KB	Output is correct
14	Correct	311 ms	115440 KB	Output is correct
15	Correct	330 ms	99420 KB	Output is correct
16	Correct	151 ms	65232 KB	Output is correct
17	Correct	267 ms	79032 KB	Output is correct
18	Correct	609 ms	124108 KB	Output is correct
19	Correct	533 ms	114520 KB	Output is correct
20	Correct	614 ms	118044 KB	Output is correct
21	Correct	280 ms	29668 KB	Output is correct
22	Correct	264 ms	27772 KB	Output is correct
23	Correct	104 ms	35824 KB	Output is correct
24	Correct	181 ms	46572 KB	Output is correct
25	Correct	901 ms	108332 KB	Output is correct
26	Correct	276 ms	115292 KB	Output is correct
27	Correct	314 ms	115504 KB	Output is correct
28	Correct	323 ms	99328 KB	Output is correct
29	Correct	154 ms	65224 KB	Output is correct
30	Correct	268 ms	79156 KB	Output is correct
31	Correct	614 ms	124108 KB	Output is correct
32	Correct	546 ms	114436 KB	Output is correct
33	Correct	588 ms	118044 KB	Output is correct

Subtask #4
27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	332 KB	Output is correct
2	Correct	4 ms	588 KB	Output is correct
3	Correct	2 ms	332 KB	Output is correct
4	Correct	3 ms	332 KB	Output is correct
5	Correct	5 ms	588 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	0 ms	204 KB	Output is correct
10	Correct	0 ms	204 KB	Output is correct
11	Correct	3 ms	332 KB	Output is correct
12	Correct	4 ms	460 KB	Output is correct
13	Correct	6 ms	716 KB	Output is correct
14	Correct	6 ms	844 KB	Output is correct
15	Correct	0 ms	204 KB	Output is correct
16	Correct	0 ms	204 KB	Output is correct
17	Correct	1 ms	204 KB	Output is correct
18	Correct	898 ms	23148 KB	Output is correct
19	Correct	256 ms	1860 KB	Output is correct
20	Correct	190 ms	1124 KB	Output is correct
21	Correct	224 ms	1336 KB	Output is correct
22	Correct	239 ms	1624 KB	Output is correct
23	Correct	234 ms	1816 KB	Output is correct
24	Correct	234 ms	1348 KB	Output is correct
25	Correct	245 ms	1520 KB	Output is correct
26	Correct	259 ms	1780 KB	Output is correct
27	Correct	389 ms	17860 KB	Output is correct
28	Correct	332 ms	9752 KB	Output is correct
29	Correct	371 ms	16288 KB	Output is correct
30	Correct	894 ms	45652 KB	Output is correct
31	Correct	3 ms	332 KB	Output is correct
32	Correct	604 ms	19248 KB	Output is correct

Subtask #5
26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	332 KB	Output is correct
2	Correct	4 ms	588 KB	Output is correct
3	Correct	2 ms	332 KB	Output is correct
4	Correct	3 ms	332 KB	Output is correct
5	Correct	5 ms	588 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	0 ms	204 KB	Output is correct
10	Correct	0 ms	204 KB	Output is correct
11	Correct	3 ms	332 KB	Output is correct
12	Correct	4 ms	460 KB	Output is correct
13	Correct	6 ms	716 KB	Output is correct
14	Correct	6 ms	844 KB	Output is correct
15	Correct	0 ms	204 KB	Output is correct
16	Correct	0 ms	204 KB	Output is correct
17	Correct	1 ms	204 KB	Output is correct
18	Correct	898 ms	23148 KB	Output is correct
19	Correct	256 ms	1860 KB	Output is correct
20	Correct	190 ms	1124 KB	Output is correct
21	Correct	224 ms	1336 KB	Output is correct
22	Correct	239 ms	1624 KB	Output is correct
23	Correct	234 ms	1816 KB	Output is correct
24	Correct	234 ms	1348 KB	Output is correct
25	Correct	245 ms	1520 KB	Output is correct
26	Correct	259 ms	1780 KB	Output is correct
27	Correct	389 ms	17860 KB	Output is correct
28	Correct	332 ms	9752 KB	Output is correct
29	Correct	371 ms	16288 KB	Output is correct
30	Correct	894 ms	45652 KB	Output is correct
31	Correct	3 ms	332 KB	Output is correct
32	Correct	604 ms	19248 KB	Output is correct
33	Correct	908 ms	108400 KB	Output is correct
34	Correct	279 ms	115252 KB	Output is correct
35	Correct	311 ms	115492 KB	Output is correct
36	Correct	337 ms	99412 KB	Output is correct
37	Correct	165 ms	67248 KB	Output is correct
38	Correct	251 ms	75320 KB	Output is correct
39	Correct	272 ms	29792 KB	Output is correct
40	Correct	267 ms	27704 KB	Output is correct
41	Correct	107 ms	35700 KB	Output is correct
42	Correct	179 ms	46528 KB	Output is correct
43	Correct	941 ms	108384 KB	Output is correct
44	Correct	276 ms	115300 KB	Output is correct
45	Correct	311 ms	115440 KB	Output is correct
46	Correct	330 ms	99420 KB	Output is correct
47	Correct	151 ms	65232 KB	Output is correct
48	Correct	267 ms	79032 KB	Output is correct
49	Correct	609 ms	124108 KB	Output is correct
50	Correct	533 ms	114520 KB	Output is correct
51	Correct	614 ms	118044 KB	Output is correct
52	Correct	280 ms	29668 KB	Output is correct
53	Correct	264 ms	27772 KB	Output is correct
54	Correct	104 ms	35824 KB	Output is correct
55	Correct	181 ms	46572 KB	Output is correct
56	Correct	901 ms	108332 KB	Output is correct
57	Correct	276 ms	115292 KB	Output is correct
58	Correct	314 ms	115504 KB	Output is correct
59	Correct	323 ms	99328 KB	Output is correct
60	Correct	154 ms	65224 KB	Output is correct
61	Correct	268 ms	79156 KB	Output is correct
62	Correct	614 ms	124108 KB	Output is correct
63	Correct	546 ms	114436 KB	Output is correct
64	Correct	588 ms	118044 KB	Output is correct
65	Correct	283 ms	20012 KB	Output is correct
66	Correct	419 ms	33084 KB	Output is correct
67	Correct	447 ms	32728 KB	Output is correct
68	Correct	434 ms	25664 KB	Output is correct
69	Correct	433 ms	25376 KB	Output is correct
70	Correct	67 ms	1020 KB	Output is correct
71	Correct	428 ms	33028 KB	Output is correct
72	Correct	452 ms	32824 KB	Output is correct
73	Correct	437 ms	25772 KB	Output is correct
74	Correct	348 ms	30568 KB	Output is correct
75	Correct	346 ms	33064 KB	Output is correct
76	Correct	364 ms	32788 KB	Output is correct
77	Correct	377 ms	25916 KB	Output is correct
78	Correct	323 ms	23924 KB	Output is correct
79	Correct	604 ms	30472 KB	Output is correct
80	Correct	652 ms	28436 KB	Output is correct
81	Correct	361 ms	36420 KB	Output is correct
82	Correct	452 ms	47264 KB	Output is correct
83	Correct	1201 ms	108972 KB	Output is correct
84	Correct	848 ms	116000 KB	Output is correct
85	Correct	671 ms	116140 KB	Output is correct
86	Correct	697 ms	100084 KB	Output is correct
87	Correct	318 ms	65860 KB	Output is correct
88	Correct	460 ms	79724 KB	Output is correct
89	Correct	842 ms	124744 KB	Output is correct
90	Correct	1050 ms	115368 KB	Output is correct
91	Correct	922 ms	118676 KB	Output is correct

답안 #471430

Compilation message

Subtask #1 11.0 / 11.0

Subtask #2 12.0 / 12.0

Subtask #3 24.0 / 24.0

Subtask #4 27.0 / 27.0

Subtask #5 26.0 / 26.0

Subtask #1
11.0 / 11.0

Subtask #2
12.0 / 12.0

Subtask #3
24.0 / 24.0

Subtask #4
27.0 / 27.0

Subtask #5
26.0 / 26.0