oj.uz

Submission #146271

# Submission time Handle Problem Language Result Execution time Memory
146271 2019-08-23T09:11:01 Z TadijaSebez Land of the Rainbow Gold (APIO17_rainbow) C++11
47 / 100
 3000 ms 35540 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);v[1].pb(p-pt(1,0));
	v[2].pb(p);v[2].pb(p-pt(0,1));
	v[3].pb(p);v[3].pb(p-pt(1,0));v[3].pb(p-pt(0,1));v[3].pb(p-pt(1,1));
}
const int N=400050;
void ckmn(int &a, int b){ a=min(a,b);}
void ckmx(int &a, int b){ a=max(a,b);}
int d;
bool comp(pt a, pt b){ return d==0?a<b:mp(a.y,a.x)<mp(b.y,b.x);}
struct KDTree
{
	int ls[N],rs[N],tsz,root,sum[N];
	pt p[N],l[N],r[N];
	KDTree(){}
	void upd_mn(int c, pt f){ ckmn(l[c].x,f.x);ckmn(l[c].y,f.y);}
	void upd_mx(int c, pt f){ ckmx(r[c].x,f.x);ckmx(r[c].y,f.y);}
	void Build(int &c, int d, vector<pt> v)
	{
		if(v.empty()) return;
		c=++tsz;
		::d=d;
		int mid=(v.size()-1)/2;
		nth_element(v.begin(),v.begin()+mid,v.end());
		p[c]=l[c]=r[c]=v[mid];sum[c]=1;
		vector<pt> u(v.begin()+mid+1,v.end());
		v.resize(mid);
		Build(ls[c],d^1,v);
		Build(rs[c],d^1,u);
		if(ls[c]) upd_mn(c,l[ls[c]]),upd_mx(c,r[ls[c]]),sum[c]+=sum[ls[c]];
		if(rs[c]) upd_mn(c,l[rs[c]]),upd_mx(c,r[rs[c]]),sum[c]+=sum[rs[c]];
	}
	void Build(vector<pt> v){ Build(root,0,v);}
	int Get(int c, int d, pt qs, pt qe)
	{
		if(!c) return 0;
		if(qs.x<=l[c].x && qs.y<=l[c].y && qe.x>=r[c].x && qe.y>=r[c].y) return sum[c];
		if(qe.x<l[c].x || qe.y<l[c].y || qs.x>r[c].x || qs.y>r[c].y) return 0;
		int ans=0;
		if(qs.x<=p[c].x && qs.y<=p[c].y && qe.x>=p[c].x && qe.y>=p[c].y) ans++;
		ans+=Get(ls[c],d^1,qs,qe);
		ans+=Get(rs[c],d^1,qs,qe);
		return ans;
	}
	ll Get(int x1, int y1, int x2, int y2)
	{
		if(x2<x1 || y2<y1) return 0;
		pt L(x1,y1),R(x2,y2);
		return (ll)(x2-x1+1)*(y2-y1+1)-Get(root,0,L,R);
	}
} KDT[4];
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());
		KDT[i].Build(v[i]);
	}
}
pt mn,mx;
void init(int R, int C, int sr, int sc, int M, char *S)
{
	pt pos(sr,sc);
	Add(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);
	}
	Build();
	mn=KDT[0].l[KDT[0].root];
	mx=KDT[0].r[KDT[0].root];
}
int colour(int x1, int y1, int x2, int y2)
{
	ll ans=KDT[0].Get(x1,y1,x2,y2)-KDT[1].Get(x1,y1,x2-1,y2)-KDT[2].Get(x1,y1,x2,y2-1)+KDT[3].Get(x1,y1,x2-1,y2-1);
	if(x1<mn.x && y1<mn.y && x2>mx.x && y2>mx.y) ans++;
	return ans;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 760 KB Output is correct
2 Correct 16 ms 888 KB Output is correct
3 Correct 6 ms 632 KB Output is correct
4 Correct 7 ms 632 KB Output is correct
5 Correct 18 ms 1144 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 2 ms 504 KB Output is correct
8 Correct 2 ms 504 KB Output is correct
9 Correct 2 ms 504 KB Output is correct
10 Correct 2 ms 504 KB Output is correct
11 Correct 7 ms 760 KB Output is correct
12 Correct 13 ms 888 KB Output is correct
13 Correct 24 ms 1016 KB Output is correct
14 Correct 31 ms 1400 KB Output is correct
15 Correct 2 ms 504 KB Output is correct
16 Correct 2 ms 504 KB Output is correct
17 Correct 2 ms 504 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 355 ms 22260 KB Output is correct
4 Correct 543 ms 35448 KB Output is correct
5 Correct 535 ms 34984 KB Output is correct
6 Correct 388 ms 31944 KB Output is correct
7 Correct 535 ms 31900 KB Output is correct
8 Correct 119 ms 11972 KB Output is correct
9 Correct 662 ms 35540 KB Output is correct
10 Correct 585 ms 34972 KB Output is correct
11 Correct 451 ms 31812 KB Output is correct
12 Correct 274 ms 32908 KB Output is correct
13 Correct 284 ms 35348 KB Output is correct
14 Correct 291 ms 35100 KB Output is correct
15 Correct 285 ms 31856 KB Output is correct
16 Correct 367 ms 28452 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 181 ms 35268 KB Output is correct
3 Correct 164 ms 35148 KB Output is correct
4 Correct 157 ms 35140 KB Output is correct
5 Correct 134 ms 27424 KB Output is correct
6 Correct 103 ms 12612 KB Output is correct
7 Correct 137 ms 17572 KB Output is correct
8 Correct 185 ms 32092 KB Output is correct
9 Correct 176 ms 29396 KB Output is correct
10 Correct 70 ms 9288 KB Output is correct
11 Correct 142 ms 21128 KB Output is correct
12 Correct 177 ms 35168 KB Output is correct
13 Correct 156 ms 35172 KB Output is correct
14 Correct 163 ms 35272 KB Output is correct
15 Correct 137 ms 27564 KB Output is correct
16 Correct 99 ms 11684 KB Output is correct
17 Correct 141 ms 17588 KB Output is correct
18 Correct 220 ms 35140 KB Output is correct
19 Correct 164 ms 35140 KB Output is correct
20 Correct 166 ms 35148 KB Output is correct
21 Correct 185 ms 32144 KB Output is correct
22 Correct 177 ms 29380 KB Output is correct
23 Correct 70 ms 9296 KB Output is correct
24 Correct 144 ms 21068 KB Output is correct
25 Correct 187 ms 35288 KB Output is correct
26 Correct 158 ms 35160 KB Output is correct
27 Correct 157 ms 35112 KB Output is correct
28 Correct 136 ms 27456 KB Output is correct
29 Correct 99 ms 11788 KB Output is correct
30 Correct 137 ms 17656 KB Output is correct
31 Correct 203 ms 35140 KB Output is correct
32 Correct 167 ms 35228 KB Output is correct
33 Correct 172 ms 35352 KB Output is correct

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 760 KB Output is correct
2 Correct 16 ms 888 KB Output is correct
3 Correct 6 ms 632 KB Output is correct
4 Correct 7 ms 632 KB Output is correct
5 Correct 18 ms 1144 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 2 ms 504 KB Output is correct
8 Correct 2 ms 504 KB Output is correct
9 Correct 2 ms 504 KB Output is correct
10 Correct 2 ms 504 KB Output is correct
11 Correct 7 ms 760 KB Output is correct
12 Correct 13 ms 888 KB Output is correct
13 Correct 24 ms 1016 KB Output is correct
14 Correct 31 ms 1400 KB Output is correct
15 Correct 2 ms 504 KB Output is correct
16 Correct 2 ms 504 KB Output is correct
17 Correct 2 ms 504 KB Output is correct
18 Execution timed out 3034 ms 22256 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 760 KB Output is correct
2 Correct 16 ms 888 KB Output is correct
3 Correct 6 ms 632 KB Output is correct
4 Correct 7 ms 632 KB Output is correct
5 Correct 18 ms 1144 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 2 ms 504 KB Output is correct
8 Correct 2 ms 504 KB Output is correct
9 Correct 2 ms 504 KB Output is correct
10 Correct 2 ms 504 KB Output is correct
11 Correct 7 ms 760 KB Output is correct
12 Correct 13 ms 888 KB Output is correct
13 Correct 24 ms 1016 KB Output is correct
14 Correct 31 ms 1400 KB Output is correct
15 Correct 2 ms 504 KB Output is correct
16 Correct 2 ms 504 KB Output is correct
17 Correct 2 ms 504 KB Output is correct
18 Execution timed out 3034 ms 22256 KB Time limit exceeded
19 Halted 0 ms 0 KB -