oj.uz

Submission #471427

# Submission time Handle Problem Language Result Execution time Memory
471427 2021-09-09T06:48:16 Z CSQ31 Land of the Rainbow Gold (APIO17_rainbow) C++17
100 / 100
 1482 ms 477316 KB 
#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
int r,c;
#define fi first
#define se second
typedef pair<int,int> pii;
struct node {
	node *L = NULL,*R=NULL;
	int val = 0;
	node(){};
	node(int v){val = v;}
	node(node *_L,node *_R){
		L = _L;
		R = _R;
		val = ((L==NULL)?0:L->val) + ((R==NULL)?0:R->val);
	}
};
const int MAXN = 2e5;
struct seg{
	vector<node*>root;
	vector<set<int>>d;
	void add(int x,int y){d[x].insert(y);}
	int r,c;
	seg(){}
	seg(int _r,int _c){
		r = _r;
		c = _c;
		root.resize(r+1);
		d.resize(r+1);
		root[0] = new node();
	}
	
	node* upd(node *v,int l,int r,int pos){
		if(l == r)return new node(v->val+1);
		int tm = (l+r)/2;
		if(pos <=tm){
			if(v->L == NULL)v->L = new node();
			return new node(upd(v->L,l,tm,pos), v->R);
		}else{
			if(v->R == NULL)v->R = new node();
			return new node(v->L, upd(v->R,tm+1,r,pos));	
		}
	}
	int query(node *b,int l,int r,int tl,int tr){
		if(l>r || !b)return 0;
		if(l==tl && r==tr)return b->val;
		int tm = (tl+tr)/2;
		return query(b->L,l,min(r,tm),tl,tm)+query(b->R,max(l,tm+1),r,tm+1,tr);
	}
	int query(int xl,int xr,int yl,int yr){
		if(xl > xr)return 0;
		return query(root[xr],yl,yr,1,c) - query(root[xl-1],yl,yr,1,c);
	}
	
	void build(){
		for(int i=1;i<=r;i++){
			root[i] = new node(root[i-1]->L,root[i-1]->R);
			for(int x:d[i])root[i] = upd(root[i],1,c,x);
		}
	}
}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 = seg(r,c);
	hedge = seg(r+1,c);
	vedge = seg(r,c+1);
	vert = seg(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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 460 KB Output is correct
2 Correct 5 ms 1612 KB Output is correct
3 Correct 3 ms 588 KB Output is correct
4 Correct 3 ms 716 KB Output is correct
5 Correct 5 ms 1852 KB Output is correct
6 Correct 1 ms 296 KB Output is correct
7 Correct 1 ms 296 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 3 ms 844 KB Output is correct
12 Correct 4 ms 1228 KB Output is correct
13 Correct 6 ms 2380 KB Output is correct
14 Correct 7 ms 2764 KB Output is correct
15 Correct 1 ms 296 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 669 ms 244908 KB Output is correct
4 Correct 1107 ms 407544 KB Output is correct
5 Correct 1082 ms 402452 KB Output is correct
6 Correct 837 ms 305928 KB Output is correct
7 Correct 981 ms 300936 KB Output is correct
8 Correct 85 ms 3868 KB Output is correct
9 Correct 1131 ms 407496 KB Output is correct
10 Correct 1111 ms 402496 KB Output is correct
11 Correct 873 ms 305880 KB Output is correct
12 Correct 757 ms 379628 KB Output is correct
13 Correct 813 ms 407488 KB Output is correct
14 Correct 821 ms 402524 KB Output is correct
15 Correct 710 ms 306248 KB Output is correct
16 Correct 710 ms 289352 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 296 KB Output is correct
2 Correct 856 ms 473656 KB Output is correct
3 Correct 542 ms 441924 KB Output is correct
4 Correct 618 ms 461172 KB Output is correct
5 Correct 575 ms 356720 KB Output is correct
6 Correct 196 ms 140384 KB Output is correct
7 Correct 350 ms 210988 KB Output is correct
8 Correct 643 ms 309748 KB Output is correct
9 Correct 554 ms 267008 KB Output is correct
10 Correct 154 ms 85392 KB Output is correct
11 Correct 360 ms 199644 KB Output is correct
12 Correct 810 ms 473788 KB Output is correct
13 Correct 563 ms 441884 KB Output is correct
14 Correct 615 ms 461160 KB Output is correct
15 Correct 481 ms 356748 KB Output is correct
16 Correct 184 ms 126024 KB Output is correct
17 Correct 317 ms 211036 KB Output is correct
18 Correct 689 ms 448860 KB Output is correct
19 Correct 721 ms 464044 KB Output is correct
20 Correct 680 ms 463812 KB Output is correct
21 Correct 658 ms 309816 KB Output is correct
22 Correct 620 ms 266820 KB Output is correct
23 Correct 158 ms 85396 KB Output is correct
24 Correct 356 ms 199596 KB Output is correct
25 Correct 828 ms 473716 KB Output is correct
26 Correct 545 ms 441992 KB Output is correct
27 Correct 655 ms 461152 KB Output is correct
28 Correct 509 ms 356672 KB Output is correct
29 Correct 195 ms 126020 KB Output is correct
30 Correct 321 ms 211120 KB Output is correct
31 Correct 667 ms 448948 KB Output is correct
32 Correct 681 ms 464032 KB Output is correct
33 Correct 673 ms 463768 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 460 KB Output is correct
2 Correct 5 ms 1612 KB Output is correct
3 Correct 3 ms 588 KB Output is correct
4 Correct 3 ms 716 KB Output is correct
5 Correct 5 ms 1852 KB Output is correct
6 Correct 1 ms 296 KB Output is correct
7 Correct 1 ms 296 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 3 ms 844 KB Output is correct
12 Correct 4 ms 1228 KB Output is correct
13 Correct 6 ms 2380 KB Output is correct
14 Correct 7 ms 2764 KB Output is correct
15 Correct 1 ms 296 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1038 ms 123012 KB Output is correct
19 Correct 257 ms 9284 KB Output is correct
20 Correct 166 ms 4468 KB Output is correct
21 Correct 202 ms 5312 KB Output is correct
22 Correct 215 ms 6528 KB Output is correct
23 Correct 261 ms 9020 KB Output is correct
24 Correct 189 ms 4892 KB Output is correct
25 Correct 204 ms 5956 KB Output is correct
26 Correct 222 ms 6916 KB Output is correct
27 Correct 380 ms 99916 KB Output is correct
28 Correct 269 ms 50244 KB Output is correct
29 Correct 351 ms 91632 KB Output is correct
30 Correct 735 ms 238696 KB Output is correct
31 Correct 3 ms 460 KB Output is correct
32 Correct 701 ms 101144 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 460 KB Output is correct
2 Correct 5 ms 1612 KB Output is correct
3 Correct 3 ms 588 KB Output is correct
4 Correct 3 ms 716 KB Output is correct
5 Correct 5 ms 1852 KB Output is correct
6 Correct 1 ms 296 KB Output is correct
7 Correct 1 ms 296 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 3 ms 844 KB Output is correct
12 Correct 4 ms 1228 KB Output is correct
13 Correct 6 ms 2380 KB Output is correct
14 Correct 7 ms 2764 KB Output is correct
15 Correct 1 ms 296 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1038 ms 123012 KB Output is correct
19 Correct 257 ms 9284 KB Output is correct
20 Correct 166 ms 4468 KB Output is correct
21 Correct 202 ms 5312 KB Output is correct
22 Correct 215 ms 6528 KB Output is correct
23 Correct 261 ms 9020 KB Output is correct
24 Correct 189 ms 4892 KB Output is correct
25 Correct 204 ms 5956 KB Output is correct
26 Correct 222 ms 6916 KB Output is correct
27 Correct 380 ms 99916 KB Output is correct
28 Correct 269 ms 50244 KB Output is correct
29 Correct 351 ms 91632 KB Output is correct
30 Correct 735 ms 238696 KB Output is correct
31 Correct 3 ms 460 KB Output is correct
32 Correct 701 ms 101144 KB Output is correct
33 Correct 856 ms 473656 KB Output is correct
34 Correct 542 ms 441924 KB Output is correct
35 Correct 618 ms 461172 KB Output is correct
36 Correct 575 ms 356720 KB Output is correct
37 Correct 196 ms 140384 KB Output is correct
38 Correct 350 ms 210988 KB Output is correct
39 Correct 643 ms 309748 KB Output is correct
40 Correct 554 ms 267008 KB Output is correct
41 Correct 154 ms 85392 KB Output is correct
42 Correct 360 ms 199644 KB Output is correct
43 Correct 810 ms 473788 KB Output is correct
44 Correct 563 ms 441884 KB Output is correct
45 Correct 615 ms 461160 KB Output is correct
46 Correct 481 ms 356748 KB Output is correct
47 Correct 184 ms 126024 KB Output is correct
48 Correct 317 ms 211036 KB Output is correct
49 Correct 689 ms 448860 KB Output is correct
50 Correct 721 ms 464044 KB Output is correct
51 Correct 680 ms 463812 KB Output is correct
52 Correct 658 ms 309816 KB Output is correct
53 Correct 620 ms 266820 KB Output is correct
54 Correct 158 ms 85396 KB Output is correct
55 Correct 356 ms 199596 KB Output is correct
56 Correct 828 ms 473716 KB Output is correct
57 Correct 545 ms 441992 KB Output is correct
58 Correct 655 ms 461152 KB Output is correct
59 Correct 509 ms 356672 KB Output is correct
60 Correct 195 ms 126020 KB Output is correct
61 Correct 321 ms 211120 KB Output is correct
62 Correct 667 ms 448948 KB Output is correct
63 Correct 681 ms 464032 KB Output is correct
64 Correct 673 ms 463768 KB Output is correct
65 Correct 669 ms 244908 KB Output is correct
66 Correct 1107 ms 407544 KB Output is correct
67 Correct 1082 ms 402452 KB Output is correct
68 Correct 837 ms 305928 KB Output is correct
69 Correct 981 ms 300936 KB Output is correct
70 Correct 85 ms 3868 KB Output is correct
71 Correct 1131 ms 407496 KB Output is correct
72 Correct 1111 ms 402496 KB Output is correct
73 Correct 873 ms 305880 KB Output is correct
74 Correct 757 ms 379628 KB Output is correct
75 Correct 813 ms 407488 KB Output is correct
76 Correct 821 ms 402524 KB Output is correct
77 Correct 710 ms 306248 KB Output is correct
78 Correct 710 ms 289352 KB Output is correct
79 Correct 1438 ms 313348 KB Output is correct
80 Correct 1482 ms 270300 KB Output is correct
81 Correct 486 ms 88928 KB Output is correct
82 Correct 640 ms 202996 KB Output is correct
83 Correct 1278 ms 477316 KB Output is correct
84 Correct 749 ms 445380 KB Output is correct
85 Correct 893 ms 464684 KB Output is correct
86 Correct 728 ms 360260 KB Output is correct
87 Correct 358 ms 129556 KB Output is correct
88 Correct 534 ms 214520 KB Output is correct
89 Correct 902 ms 452396 KB Output is correct
90 Correct 1103 ms 467480 KB Output is correct
91 Correct 1032 ms 467180 KB Output is correct