oj.uz

Submission #543324

# Submission time Handle Problem Language Result Execution time Memory
543324 2022-03-30T08:52:16 Z amunduzbaev Land of the Rainbow Gold (APIO17_rainbow) C++17
12 / 100
 1579 ms 233696 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
2 3 2 3
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) {
	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);
	//~ cout<<V<<" "<<ee<<endl;
	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);
	//~ cout<<V<<" "<<ee<<" "<<F<<"\n";
	return (2 - V + ee - F - 1);
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 144460 KB Output is correct
2 Correct 261 ms 144984 KB Output is correct
3 Incorrect 224 ms 144600 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 231 ms 144404 KB Output is correct
2 Correct 227 ms 144216 KB Output is correct
3 Correct 1051 ms 197068 KB Output is correct
4 Correct 1566 ms 231576 KB Output is correct
5 Correct 1579 ms 230772 KB Output is correct
6 Correct 1260 ms 213040 KB Output is correct
7 Correct 1313 ms 210816 KB Output is correct
8 Correct 346 ms 148116 KB Output is correct
9 Correct 1458 ms 231460 KB Output is correct
10 Correct 1498 ms 230748 KB Output is correct
11 Correct 1238 ms 212508 KB Output is correct
12 Correct 1241 ms 226544 KB Output is correct
13 Correct 1164 ms 231372 KB Output is correct
14 Correct 1171 ms 230712 KB Output is correct
15 Correct 1035 ms 213160 KB Output is correct
16 Correct 1194 ms 210332 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 144284 KB Output is correct
2 Correct 1214 ms 228756 KB Output is correct
3 Correct 889 ms 227788 KB Output is correct
4 Correct 838 ms 233696 KB Output is correct
5 Correct 782 ms 207660 KB Output is correct
6 Correct 375 ms 160440 KB Output is correct
7 Incorrect 491 ms 175672 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 144460 KB Output is correct
2 Correct 261 ms 144984 KB Output is correct
3 Incorrect 224 ms 144600 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 144460 KB Output is correct
2 Correct 261 ms 144984 KB Output is correct
3 Incorrect 224 ms 144600 KB Output isn't correct
4 Halted 0 ms 0 KB -