oj.uz

Submission #146287

# Submission time Handle Problem Language Result Execution time Memory
146287 2019-08-23T09:54:15 Z TadijaSebez Land of the Rainbow Gold (APIO17_rainbow) C++11
100 / 100
 845 ms 149024 KB 
#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define ll long long
struct pt{ int x,y;pt(){}pt(int a, int b):x(a),y(b){}};
pt operator - (pt a, pt b){ return pt(a.x-b.x,a.y-b.y);}
bool operator < (pt a, pt b){ return mp(a.x,a.y)<mp(b.x,b.y);}
bool operator == (pt a, pt b){ return mp(a.x,a.y)==mp(b.x,b.y);}
vector<pt> v[4];
void Add(pt p)
{
	v[0].pb(p);
	v[1].pb(p);if(p.x!=1) v[1].pb(p-pt(1,0));
	v[2].pb(p);if(p.y!=1) v[2].pb(p-pt(0,1));
	v[3].pb(p);if(p.x!=1) v[3].pb(p-pt(1,0));if(p.y!=1) v[3].pb(p-pt(0,1));if(min(p.x,p.y)!=1) v[3].pb(p-pt(1,1));
}
void ckmn(int &a, int b){ a=min(a,b);}
void ckmx(int &a, int b){ a=max(a,b);}
const int N=200050;
const int M=900050;
const int H=20*M;
int ls[H],rs[H],tsz,sum[H],n,m,root[4][N];
void Set(int p, int &c, int ss, int se, int qi)
{
	c=++tsz;ls[c]=ls[p];rs[c]=rs[p];sum[c]=sum[p]+1;
	if(ss==se) return;
	int mid=ss+se>>1;
	if(qi<=mid) Set(ls[p],ls[c],ss,mid,qi);
	else Set(rs[p],rs[c],mid+1,se,qi);
}
int Get(int p, int c, int ss, int se, int qs, int qe)
{
	if(qs>qe || qs>se || ss>qe) return 0;
	if(qs<=ss && qe>=se) return sum[c]-sum[p];
	int mid=ss+se>>1;
	return Get(ls[p],ls[c],ss,mid,qs,qe)+Get(rs[p],rs[c],mid+1,se,qs,qe);
}
ll Get(int t, int x1, int y1, int x2, int y2){ return (ll)(x2-x1+1)*(y2-y1+1)-Get(root[t][x1-1],root[t][x2],1,N,y1,y2);}
void Build()
{
	for(int i=0;i<4;i++)
	{
		sort(v[i].begin(),v[i].end());
		v[i].resize(unique(v[i].begin(),v[i].end())-v[i].begin());
		for(int j=1,k=0;j<N;j++)
		{
			root[i][j]=root[i][j-1];
			for(;k<v[i].size() && v[i][k].x==j;k++) Set(root[i][j],root[i][j],1,N,v[i][k].y);
		}
	}
}
pt mn,mx;
void init(int R, int C, int sr, int sc, int M, char *S)
{
	n=R,m=C;
	pt pos(sr,sc);
	Add(pos);
	mn=mx=pos;
	for(int i=0;i<M;i++)
	{
		if(S[i]=='N') pos.x--;
		if(S[i]=='S') pos.x++;
		if(S[i]=='W') pos.y--;
		if(S[i]=='E') pos.y++;
		Add(pos);
		ckmn(mn.x,pos.x);ckmn(mn.y,pos.y);
		ckmx(mx.x,pos.x);ckmx(mx.y,pos.y);
	}
	Build();
}
int colour(int x1, int y1, int x2, int y2)
{
	ll ans=Get(0,x1,y1,x2,y2)-Get(1,x1,y1,x2-1,y2)-Get(2,x1,y1,x2,y2-1)+Get(3,x1,y1,x2-1,y2-1);
	if(x1<mn.x && y1<mn.y && x2>mx.x && y2>mx.y) ans++;
	return ans;
}

Compilation message

rainbow.cpp: In function 'void Set(int, int&, int, int, int)':
rainbow.cpp:29:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
rainbow.cpp: In function 'int Get(int, int, int, int, int, int)':
rainbow.cpp:37:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
rainbow.cpp: In function 'void Build()':
rainbow.cpp:50:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(;k<v[i].size() && v[i][k].x==j;k++) Set(root[i][j],root[i][j],1,N,v[i][k].y);
         ~^~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3704 KB Output is correct
2 Correct 11 ms 4728 KB Output is correct
3 Correct 8 ms 3708 KB Output is correct
4 Correct 8 ms 3832 KB Output is correct
5 Correct 12 ms 5112 KB Output is correct
6 Correct 6 ms 3448 KB Output is correct
7 Correct 6 ms 3448 KB Output is correct
8 Correct 6 ms 3448 KB Output is correct
9 Correct 6 ms 3448 KB Output is correct
10 Correct 6 ms 3448 KB Output is correct
11 Correct 9 ms 3960 KB Output is correct
12 Correct 10 ms 4472 KB Output is correct
13 Correct 12 ms 5368 KB Output is correct
14 Correct 14 ms 5880 KB Output is correct
15 Correct 7 ms 3448 KB Output is correct
16 Correct 7 ms 3448 KB Output is correct
17 Correct 6 ms 3448 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 3448 KB Output is correct
2 Correct 6 ms 3448 KB Output is correct
3 Correct 462 ms 75216 KB Output is correct
4 Correct 614 ms 120644 KB Output is correct
5 Correct 605 ms 118692 KB Output is correct
6 Correct 508 ms 91816 KB Output is correct
7 Correct 548 ms 87120 KB Output is correct
8 Correct 250 ms 11048 KB Output is correct
9 Correct 608 ms 119852 KB Output is correct
10 Correct 607 ms 118496 KB Output is correct
11 Correct 517 ms 91972 KB Output is correct
12 Correct 355 ms 117060 KB Output is correct
13 Correct 361 ms 120516 KB Output is correct
14 Correct 358 ms 118920 KB Output is correct
15 Correct 325 ms 91968 KB Output is correct
16 Correct 465 ms 80804 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 3448 KB Output is correct
2 Correct 291 ms 143204 KB Output is correct
3 Correct 272 ms 145500 KB Output is correct
4 Correct 273 ms 143184 KB Output is correct
5 Correct 228 ms 110404 KB Output is correct
6 Correct 128 ms 36052 KB Output is correct
7 Correct 181 ms 60616 KB Output is correct
8 Correct 248 ms 110276 KB Output is correct
9 Correct 245 ms 101780 KB Output is correct
10 Correct 95 ms 33236 KB Output is correct
11 Correct 201 ms 75972 KB Output is correct
12 Correct 292 ms 143040 KB Output is correct
13 Correct 271 ms 145348 KB Output is correct
14 Correct 275 ms 143256 KB Output is correct
15 Correct 225 ms 110404 KB Output is correct
16 Correct 120 ms 31044 KB Output is correct
17 Correct 182 ms 60612 KB Output is correct
18 Correct 311 ms 142668 KB Output is correct
19 Correct 237 ms 120696 KB Output is correct
20 Correct 238 ms 120644 KB Output is correct
21 Correct 249 ms 110272 KB Output is correct
22 Correct 246 ms 101828 KB Output is correct
23 Correct 96 ms 33236 KB Output is correct
24 Correct 203 ms 75844 KB Output is correct
25 Correct 294 ms 143044 KB Output is correct
26 Correct 274 ms 145200 KB Output is correct
27 Correct 275 ms 143044 KB Output is correct
28 Correct 228 ms 110404 KB Output is correct
29 Correct 119 ms 31044 KB Output is correct
30 Correct 183 ms 60608 KB Output is correct
31 Correct 310 ms 142660 KB Output is correct
32 Correct 235 ms 120624 KB Output is correct
33 Correct 239 ms 120772 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3704 KB Output is correct
2 Correct 11 ms 4728 KB Output is correct
3 Correct 8 ms 3708 KB Output is correct
4 Correct 8 ms 3832 KB Output is correct
5 Correct 12 ms 5112 KB Output is correct
6 Correct 6 ms 3448 KB Output is correct
7 Correct 6 ms 3448 KB Output is correct
8 Correct 6 ms 3448 KB Output is correct
9 Correct 6 ms 3448 KB Output is correct
10 Correct 6 ms 3448 KB Output is correct
11 Correct 9 ms 3960 KB Output is correct
12 Correct 10 ms 4472 KB Output is correct
13 Correct 12 ms 5368 KB Output is correct
14 Correct 14 ms 5880 KB Output is correct
15 Correct 7 ms 3448 KB Output is correct
16 Correct 7 ms 3448 KB Output is correct
17 Correct 6 ms 3448 KB Output is correct
18 Correct 672 ms 80004 KB Output is correct
19 Correct 227 ms 10232 KB Output is correct
20 Correct 174 ms 7416 KB Output is correct
21 Correct 187 ms 8184 KB Output is correct
22 Correct 204 ms 8724 KB Output is correct
23 Correct 226 ms 10180 KB Output is correct
24 Correct 182 ms 8292 KB Output is correct
25 Correct 194 ms 8864 KB Output is correct
26 Correct 205 ms 9208 KB Output is correct
27 Correct 437 ms 68628 KB Output is correct
28 Correct 351 ms 40640 KB Output is correct
29 Correct 437 ms 63964 KB Output is correct
30 Correct 664 ms 146344 KB Output is correct
31 Correct 10 ms 3704 KB Output is correct
32 Correct 592 ms 69188 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3704 KB Output is correct
2 Correct 11 ms 4728 KB Output is correct
3 Correct 8 ms 3708 KB Output is correct
4 Correct 8 ms 3832 KB Output is correct
5 Correct 12 ms 5112 KB Output is correct
6 Correct 6 ms 3448 KB Output is correct
7 Correct 6 ms 3448 KB Output is correct
8 Correct 6 ms 3448 KB Output is correct
9 Correct 6 ms 3448 KB Output is correct
10 Correct 6 ms 3448 KB Output is correct
11 Correct 9 ms 3960 KB Output is correct
12 Correct 10 ms 4472 KB Output is correct
13 Correct 12 ms 5368 KB Output is correct
14 Correct 14 ms 5880 KB Output is correct
15 Correct 7 ms 3448 KB Output is correct
16 Correct 7 ms 3448 KB Output is correct
17 Correct 6 ms 3448 KB Output is correct
18 Correct 672 ms 80004 KB Output is correct
19 Correct 227 ms 10232 KB Output is correct
20 Correct 174 ms 7416 KB Output is correct
21 Correct 187 ms 8184 KB Output is correct
22 Correct 204 ms 8724 KB Output is correct
23 Correct 226 ms 10180 KB Output is correct
24 Correct 182 ms 8292 KB Output is correct
25 Correct 194 ms 8864 KB Output is correct
26 Correct 205 ms 9208 KB Output is correct
27 Correct 437 ms 68628 KB Output is correct
28 Correct 351 ms 40640 KB Output is correct
29 Correct 437 ms 63964 KB Output is correct
30 Correct 664 ms 146344 KB Output is correct
31 Correct 10 ms 3704 KB Output is correct
32 Correct 592 ms 69188 KB Output is correct
33 Correct 291 ms 143204 KB Output is correct
34 Correct 272 ms 145500 KB Output is correct
35 Correct 273 ms 143184 KB Output is correct
36 Correct 228 ms 110404 KB Output is correct
37 Correct 128 ms 36052 KB Output is correct
38 Correct 181 ms 60616 KB Output is correct
39 Correct 248 ms 110276 KB Output is correct
40 Correct 245 ms 101780 KB Output is correct
41 Correct 95 ms 33236 KB Output is correct
42 Correct 201 ms 75972 KB Output is correct
43 Correct 292 ms 143040 KB Output is correct
44 Correct 271 ms 145348 KB Output is correct
45 Correct 275 ms 143256 KB Output is correct
46 Correct 225 ms 110404 KB Output is correct
47 Correct 120 ms 31044 KB Output is correct
48 Correct 182 ms 60612 KB Output is correct
49 Correct 311 ms 142668 KB Output is correct
50 Correct 237 ms 120696 KB Output is correct
51 Correct 238 ms 120644 KB Output is correct
52 Correct 249 ms 110272 KB Output is correct
53 Correct 246 ms 101828 KB Output is correct
54 Correct 96 ms 33236 KB Output is correct
55 Correct 203 ms 75844 KB Output is correct
56 Correct 294 ms 143044 KB Output is correct
57 Correct 274 ms 145200 KB Output is correct
58 Correct 275 ms 143044 KB Output is correct
59 Correct 228 ms 110404 KB Output is correct
60 Correct 119 ms 31044 KB Output is correct
61 Correct 183 ms 60608 KB Output is correct
62 Correct 310 ms 142660 KB Output is correct
63 Correct 235 ms 120624 KB Output is correct
64 Correct 239 ms 120772 KB Output is correct
65 Correct 827 ms 113872 KB Output is correct
66 Correct 845 ms 105408 KB Output is correct
67 Correct 415 ms 36920 KB Output is correct
68 Correct 519 ms 79428 KB Output is correct
69 Correct 685 ms 146724 KB Output is correct
70 Correct 580 ms 149024 KB Output is correct
71 Correct 599 ms 146756 KB Output is correct
72 Correct 524 ms 114012 KB Output is correct
73 Correct 362 ms 34744 KB Output is correct
74 Correct 424 ms 64368 KB Output is correct
75 Correct 550 ms 146376 KB Output is correct
76 Correct 633 ms 124356 KB Output is correct
77 Correct 572 ms 124152 KB Output is correct
78 Correct 462 ms 75216 KB Output is correct
79 Correct 614 ms 120644 KB Output is correct
80 Correct 605 ms 118692 KB Output is correct
81 Correct 508 ms 91816 KB Output is correct
82 Correct 548 ms 87120 KB Output is correct
83 Correct 250 ms 11048 KB Output is correct
84 Correct 608 ms 119852 KB Output is correct
85 Correct 607 ms 118496 KB Output is correct
86 Correct 517 ms 91972 KB Output is correct
87 Correct 355 ms 117060 KB Output is correct
88 Correct 361 ms 120516 KB Output is correct
89 Correct 358 ms 118920 KB Output is correct
90 Correct 325 ms 91968 KB Output is correct
91 Correct 465 ms 80804 KB Output is correct