oj.uz

Submission #543338

# Submission time Handle Problem Language Result Execution time Memory
543338 2022-03-30T10:13:46 Z amunduzbaev Land of the Rainbow Gold (APIO17_rainbow) C++17
12 / 100
 1545 ms 232400 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

*/

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);
	V += (ry - ly + 2 - ver.get(lx, lx, ly, ry + 1));
	ee += (ry - ly + 1 - ed[0].get(lx, lx, ly, ry));
	
	V += (ry - ly + 2 - ver.get(rx + 1, rx + 1, ly, ry + 1));
	ee += (ry - ly + 1 - ed[0].get(rx + 1, rx + 1, ly, ry));
	
	V += (rx - lx + 2 - ver.get(lx, rx + 1, ly, ly));
	ee += (rx - lx + 1 - ed[1].get(lx, rx, ly, ly));
	
	V += (rx - lx + 2 - ver.get(lx, rx + 1, ry + 1, ry + 1));
	ee += (rx - lx + 1 - ed[1].get(lx, rx, ry + 1, ry + 1));
	
	if(!tot.count({lx, ly})) V--;
	if(!tot.count({lx, ry + 1})) V--;
	if(!tot.count({rx + 1, ly})) V--;
	if(!tot.count({rx + 1, ry + 1})) V--;
	
	int F = sq.get(lx, rx, ly, ry);
	assert(1 - V + ee - F >= 0);
	return (1 - V + ee - F);
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 75852 KB Output is correct
2 Correct 49 ms 76696 KB Output is correct
3 Incorrect 44 ms 75772 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 41 ms 75460 KB Output is correct
2 Correct 39 ms 75348 KB Output is correct
3 Correct 1061 ms 155416 KB Output is correct
4 Correct 1522 ms 215400 KB Output is correct
5 Correct 1519 ms 212672 KB Output is correct
6 Correct 1195 ms 188484 KB Output is correct
7 Correct 1362 ms 179600 KB Output is correct
8 Correct 237 ms 76176 KB Output is correct
9 Correct 1435 ms 215084 KB Output is correct
10 Correct 1545 ms 212844 KB Output is correct
11 Correct 1217 ms 186656 KB Output is correct
12 Correct 1279 ms 206740 KB Output is correct
13 Correct 1124 ms 213720 KB Output is correct
14 Correct 1077 ms 211992 KB Output is correct
15 Correct 946 ms 188244 KB Output is correct
16 Correct 1144 ms 182456 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 75416 KB Output is correct
2 Correct 1108 ms 213812 KB Output is correct
3 Correct 726 ms 232400 KB Output is correct
4 Correct 661 ms 232024 KB Output is correct
5 Correct 627 ms 187904 KB Output is correct
6 Correct 180 ms 102284 KB Output is correct
7 Incorrect 318 ms 127572 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 75852 KB Output is correct
2 Correct 49 ms 76696 KB Output is correct
3 Incorrect 44 ms 75772 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 75852 KB Output is correct
2 Correct 49 ms 76696 KB Output is correct
3 Incorrect 44 ms 75772 KB Output isn't correct
4 Halted 0 ms 0 KB -