oj.uz

Submission #543334

# Submission time Handle Problem Language Result Execution time Memory
543334 2022-03-30T10:01:49 Z amunduzbaev Land of the Rainbow Gold (APIO17_rainbow) C++17
12 / 100
 1655 ms 232456 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);
	return (1 - V + ee - F);
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 75644 KB Output is correct
2 Correct 49 ms 76736 KB Output is correct
3 Incorrect 44 ms 75764 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 38 ms 75444 KB Output is correct
2 Correct 40 ms 75340 KB Output is correct
3 Correct 1016 ms 155688 KB Output is correct
4 Correct 1655 ms 215480 KB Output is correct
5 Correct 1635 ms 212792 KB Output is correct
6 Correct 1199 ms 188884 KB Output is correct
7 Correct 1269 ms 179948 KB Output is correct
8 Correct 253 ms 76388 KB Output is correct
9 Correct 1448 ms 215196 KB Output is correct
10 Correct 1567 ms 212904 KB Output is correct
11 Correct 1275 ms 187028 KB Output is correct
12 Correct 1281 ms 206908 KB Output is correct
13 Correct 1196 ms 213952 KB Output is correct
14 Correct 1152 ms 212272 KB Output is correct
15 Correct 1048 ms 188392 KB Output is correct
16 Correct 1222 ms 182640 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 75400 KB Output is correct
2 Correct 1123 ms 213896 KB Output is correct
3 Correct 692 ms 232456 KB Output is correct
4 Correct 663 ms 232180 KB Output is correct
5 Correct 620 ms 188056 KB Output is correct
6 Correct 181 ms 102344 KB Output is correct
7 Incorrect 306 ms 127792 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 75644 KB Output is correct
2 Correct 49 ms 76736 KB Output is correct
3 Incorrect 44 ms 75764 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 75644 KB Output is correct
2 Correct 49 ms 76736 KB Output is correct
3 Incorrect 44 ms 75764 KB Output isn't correct
4 Halted 0 ms 0 KB -