oj.uz

Submission #543394

# Submission time Handle Problem Language Result Execution time Memory
543394 2022-03-30T13:16:43 Z amunduzbaev Land of the Rainbow Gold (APIO17_rainbow) C++17
12 / 100
 1628 ms 232268 KB 
#include "rainbow.h"
#include "bits/stdc++.h"
using namespace std;
#ifndef EVAL
#include "grader.cpp"
#endif

#define int long long 
#define i32 int32_t
#define ar array
const int N = 2e5 + 5;

struct MSST{
	vector<int> tree[N << 2];
	void add(int i, int y, int lx = 0, int rx = N, int x = 1){
		tree[x].push_back(y);
		if(lx == rx) return;
		int m = (lx + rx) >> 1;
		if(i <= m) add(i, y, lx, m, x<<1);
		else add(i, y, m+1, rx, x<<1|1);
	}
	
	void build(int lx = 0, int rx = N, int x = 1){
		sort(tree[x].begin(), tree[x].end());
		if(lx == rx) return;
		int m = (lx + rx) >> 1;
		build(lx, m, x<<1), build(m+1, rx, x<<1|1);
	}
	
	int get(int l, int r, int l_, int r_, int lx = 0, int rx = N, int x = 1){
		if(lx > r || rx < l) return 0;
		if(lx >= l && rx <= r){
			auto R = upper_bound(tree[x].begin(), tree[x].end(), r_);
			auto L = lower_bound(tree[x].begin(), tree[x].end(), l_);
			return R - L;
		} int m = (lx + rx) >> 1;
		return get(l, r, l_, r_, lx, m, x<<1) + get(l, r, l_, r_, m+1, rx, x<<1|1);
	}
}ed[2], ver, sq; //, ver, sq;
set<ar<int, 2>> ss, tot, is[2];

void init(i32 n, i32 m, i32 x, i32 y, i32 k, char *s) {
	ss.insert({x, y});
	for(int i=0;i<k;i++){
		if(s[i] == 'N') x--;
		if(s[i] == 'S') x++;
		if(s[i] == 'W') y--;
		if(s[i] == 'E') y++;
		ss.insert({x, y});
	}
	
	for(auto x : ss){
		//~ cout<<x[0]<<" "<<x[1]<<"\n";
		is[0].insert(x);
		is[0].insert({x[0] + 1, x[1]});
		is[1].insert(x);
		is[1].insert({x[0], x[1] + 1});
		tot.insert(x);
		tot.insert({x[0] + 1, x[1]});
		tot.insert({x[0], x[1] + 1});
		tot.insert({x[0] + 1, x[1] + 1});
		sq.add(x[0], x[1]);
	}
	
	for(auto x : tot){
		if(is[0].count(x)) ed[0].add(x[0], x[1]);
		if(is[1].count(x)) ed[1].add(x[0], x[1]);
		ver.add(x[0], x[1]);
	}
	
	ed[0].build();
	ed[1].build();
	ver.build();
	sq.build();
}

/*

6 4 9 4
3 3
NWESSWEWS
2 3 2 3
3 2 4 4
5 3 6 4
1 2 5 3

13 13 13 1
6 8
WWWEENWEEWEWE
3 4 10 13

*/

i32 colour(i32 lx, i32 ly, i32 rx, i32 ry) {
	if(lx > rx) swap(lx, rx);
	if(ly > ry) swap(ly, ry);
	int ee = ed[0].get(lx, rx + 1, ly, ry);
	ee += ed[1].get(lx, rx, ly, ry + 1);
	int V = ver.get(lx, rx + 1, ly, ry + 1);
	int tmp = 0, tt = 0;
	tmp += ver.get(lx, lx, ly, ry + 1);
	tt += ed[0].get(lx, lx, ly, ry);
	
	tmp += ver.get(rx + 1, rx + 1, ly, ry + 1);
	tt += ed[0].get(rx + 1, rx + 1, ly, ry);
	
	if(lx < rx) tmp += ver.get(lx + 1, rx, ly, ly);
	tt += ed[1].get(lx, rx, ly, ly);
	
	if(lx < rx) tmp += ver.get(lx + 1, rx, ry + 1, ry + 1);
	tt += ed[1].get(lx, rx, ry + 1, ry + 1);
	
	int v = (rx - lx + ry - ly + 2) * 2;
	V += (v - tmp);
	ee += (v - tt);
	//~ cout<<tmp<<" "<<tt<<"\n";
	int F = sq.get(lx, rx, ly, ry);
	//~ assert(1 - V + ee - F >= 0);
	int res = (1 - V + ee - F);
	if(!res){
		if(F != (rx - lx + 1) * (ry - ly + 1)) res++;
	}
	return res;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 75724 KB Output is correct
2 Correct 48 ms 76720 KB Output is correct
3 Incorrect 44 ms 75684 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 75416 KB Output is correct
2 Correct 41 ms 75364 KB Output is correct
3 Correct 920 ms 156064 KB Output is correct
4 Correct 1398 ms 215800 KB Output is correct
5 Correct 1320 ms 213176 KB Output is correct
6 Correct 1088 ms 189228 KB Output is correct
7 Correct 1096 ms 180256 KB Output is correct
8 Correct 266 ms 76824 KB Output is correct
9 Correct 1498 ms 215620 KB Output is correct
10 Correct 1628 ms 213692 KB Output is correct
11 Correct 1143 ms 187532 KB Output is correct
12 Correct 1303 ms 207648 KB Output is correct
13 Correct 1132 ms 214640 KB Output is correct
14 Correct 1095 ms 212956 KB Output is correct
15 Correct 958 ms 189156 KB Output is correct
16 Correct 1301 ms 183304 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 75444 KB Output is correct
2 Correct 1250 ms 213904 KB Output is correct
3 Correct 948 ms 232268 KB Output is correct
4 Correct 812 ms 232180 KB Output is correct
5 Correct 765 ms 187984 KB Output is correct
6 Correct 268 ms 102324 KB Output is correct
7 Incorrect 384 ms 127732 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 75724 KB Output is correct
2 Correct 48 ms 76720 KB Output is correct
3 Incorrect 44 ms 75684 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 75724 KB Output is correct
2 Correct 48 ms 76720 KB Output is correct
3 Incorrect 44 ms 75684 KB Output isn't correct
4 Halted 0 ms 0 KB -