oj.uz

Submission #471429

# Submission time Handle Problem Language Result Execution time Memory
471429 2021-09-09T07:08:02 Z CSQ31 Land of the Rainbow Gold (APIO17_rainbow) C++17
24 / 100
 948 ms 124116 KB 
#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;
	int i = 0;
	do{
		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);
		char c = S[i];
		if(c =='N')x--;
		if(c =='S')x++;
		if(c =='W')y--;
		if(c =='E')y++;
		i++;
	}
	while(i<M);
	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
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 948 ms 108220 KB Output is correct
3 Correct 290 ms 115284 KB Output is correct
4 Correct 320 ms 115500 KB Output is correct
5 Correct 336 ms 99420 KB Output is correct
6 Correct 172 ms 67220 KB Output is correct
7 Correct 246 ms 75324 KB Output is correct
8 Correct 293 ms 29668 KB Output is correct
9 Correct 305 ms 27864 KB Output is correct
10 Correct 103 ms 35756 KB Output is correct
11 Correct 179 ms 46528 KB Output is correct
12 Correct 929 ms 108336 KB Output is correct
13 Correct 275 ms 115160 KB Output is correct
14 Correct 305 ms 115508 KB Output is correct
15 Correct 335 ms 99520 KB Output is correct
16 Correct 155 ms 65184 KB Output is correct
17 Correct 270 ms 79064 KB Output is correct
18 Correct 641 ms 124116 KB Output is correct
19 Correct 539 ms 114548 KB Output is correct
20 Correct 582 ms 117984 KB Output is correct
21 Correct 284 ms 29796 KB Output is correct
22 Correct 262 ms 27796 KB Output is correct
23 Correct 127 ms 35904 KB Output is correct
24 Correct 180 ms 46600 KB Output is correct
25 Correct 913 ms 108428 KB Output is correct
26 Correct 278 ms 115244 KB Output is correct
27 Correct 317 ms 115556 KB Output is correct
28 Correct 338 ms 99456 KB Output is correct
29 Correct 161 ms 65224 KB Output is correct
30 Correct 272 ms 79276 KB Output is correct
31 Correct 605 ms 124084 KB Output is correct
32 Correct 616 ms 114592 KB Output is correct
33 Correct 644 ms 117948 KB Output is correct

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -