oj.uz

Submission #543345

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

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 75716 KB Output is correct
2 Correct 47 ms 76596 KB Output is correct
3 Incorrect 44 ms 75760 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 75412 KB Output is correct
2 Correct 38 ms 75416 KB Output is correct
3 Correct 852 ms 155272 KB Output is correct
4 Correct 1247 ms 215388 KB Output is correct
5 Correct 1245 ms 212564 KB Output is correct
6 Correct 992 ms 188612 KB Output is correct
7 Correct 1008 ms 179704 KB Output is correct
8 Correct 216 ms 76196 KB Output is correct
9 Correct 1165 ms 214988 KB Output is correct
10 Correct 1222 ms 212740 KB Output is correct
11 Correct 986 ms 186648 KB Output is correct
12 Correct 1171 ms 206636 KB Output is correct
13 Correct 1035 ms 213696 KB Output is correct
14 Correct 1031 ms 211956 KB Output is correct
15 Correct 894 ms 188168 KB Output is correct
16 Correct 961 ms 182312 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 75348 KB Output is correct
2 Correct 1105 ms 213800 KB Output is correct
3 Correct 658 ms 232456 KB Output is correct
4 Correct 658 ms 232080 KB Output is correct
5 Correct 587 ms 187900 KB Output is correct
6 Correct 172 ms 102200 KB Output is correct
7 Incorrect 309 ms 127644 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 75716 KB Output is correct
2 Correct 47 ms 76596 KB Output is correct
3 Incorrect 44 ms 75760 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 75716 KB Output is correct
2 Correct 47 ms 76596 KB Output is correct
3 Incorrect 44 ms 75760 KB Output isn't correct
4 Halted 0 ms 0 KB -