oj.uz

Submission #543328

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

#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){
		tree[x].push_back(-1);
		tree[x].push_back(N);
		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;
vector<int> row[N], col[N], erow[N], ecol[N];
set<ar<int, 2>> ss, tot, is[2];

void init(int n, int m, int x, int y, int 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]), erow[x[0]].push_back(x[1]);
		if(is[1].count(x)) ed[1].add(x[0], x[1]), ecol[x[1]].push_back(x[0]);
		ver.add(x[0], x[1]);
		//~ cout<<x[0]<<" "<<x[1]<<"\n";
		auto t = x; t[0]++, t[1]++;
		row[x[0]].push_back(x[1]);
		col[x[1]].push_back(x[0]);
	}
	
	ed[0].build();
	ed[1].build();
	ver.build();
	sq.build();
	for(int i=0;i<N;i++){
		sort(row[i].begin(), row[i].end());
		sort(col[i].begin(), col[i].end());
		sort(erow[i].begin(), erow[i].end());
		sort(ecol[i].begin(), ecol[i].end());
	}
}

/*

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

*/

ar<int, 2> get_r(int x, int l, int r){
	auto R = upper_bound(row[x].begin(), row[x].end(), r);
	auto L = lower_bound(row[x].begin(), row[x].end(), l);
	int v = R - L;
	r--;
	R = upper_bound(erow[x].begin(), erow[x].end(), r);
	L = lower_bound(erow[x].begin(), erow[x].end(), l);
	int e = R - L;
	return {v, e};
}


ar<int, 2> get_l(int x, int l, int r){
	auto R = upper_bound(col[x].begin(), col[x].end(), r);
	auto L = lower_bound(col[x].begin(), col[x].end(), l);
	int v = R - L;
	r--;
	R = upper_bound(ecol[x].begin(), ecol[x].end(), r);
	L = lower_bound(ecol[x].begin(), ecol[x].end(), l);
	int e = R - L;
	return {v, e};
}

int colour(int lx, int ly, int rx, int 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);
	auto t = get_r(lx, ly, ry + 1);
	V += (ry - ly + 2 - t[0]);
	ee += (ry - ly + 1 - t[1]);
	
	t = get_r(rx + 1, ly, ry + 1);
	V += (ry - ly + 2 - t[0]);
	ee += (ry - ly + 1 - t[1]);
	
	t = get_l(ly, lx, rx + 1);
	V += (rx - lx + 2 - t[0]);
	ee += (rx - lx + 1 - t[1]);
	
	t = get_l(ry + 1, lx, rx + 1);
	V += (rx - lx + 2 - t[0]);
	ee += (rx - lx + 1 - t[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 237 ms 144524 KB Output is correct
2 Correct 275 ms 145004 KB Output is correct
3 Incorrect 242 ms 144588 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 244 ms 144328 KB Output is correct
2 Correct 235 ms 144240 KB Output is correct
3 Correct 1162 ms 195584 KB Output is correct
4 Correct 1597 ms 230012 KB Output is correct
5 Correct 1618 ms 229028 KB Output is correct
6 Correct 1283 ms 211384 KB Output is correct
7 Correct 1344 ms 209008 KB Output is correct
8 Correct 353 ms 146424 KB Output is correct
9 Correct 1449 ms 229900 KB Output is correct
10 Correct 1488 ms 229388 KB Output is correct
11 Correct 1231 ms 210956 KB Output is correct
12 Correct 1246 ms 225036 KB Output is correct
13 Correct 1175 ms 230152 KB Output is correct
14 Correct 1163 ms 229020 KB Output is correct
15 Correct 1038 ms 211628 KB Output is correct
16 Correct 1179 ms 208760 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 144288 KB Output is correct
2 Correct 1214 ms 228756 KB Output is correct
3 Correct 850 ms 227836 KB Output is correct
4 Correct 845 ms 233764 KB Output is correct
5 Correct 760 ms 207640 KB Output is correct
6 Correct 369 ms 160460 KB Output is correct
7 Incorrect 484 ms 175624 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 237 ms 144524 KB Output is correct
2 Correct 275 ms 145004 KB Output is correct
3 Incorrect 242 ms 144588 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 237 ms 144524 KB Output is correct
2 Correct 275 ms 145004 KB Output is correct
3 Incorrect 242 ms 144588 KB Output isn't correct
4 Halted 0 ms 0 KB -