oj.uz

Submission #885417

# Submission time Handle Problem Language Result Execution time Memory
885417 2023-12-09T15:48:58 Z pubin06 Land of the Rainbow Gold (APIO17_rainbow) C++14
12 / 100
 170 ms 193228 KB 
#include "rainbow.h"
#include <bits/stdc++.h>
#define sz(v) (int)(v).size()
using namespace std;
 
const int MXn = 2e5 + 5;
const int dx[] = {1, 0, 1};
const int dy[] = {0, 1, 1};
 
int n, m;
struct PST {
	vector<int> val, idL, idR;
	void resiz(int s) {
		val.resize(s + 3, 0);
		idL.resize(s + 3, -1);
		idR.resize(s + 3, -1);
	}
	int no = 0;
	int build(int l = 1, int r = n) {
		int cur = ++no;
		assert(cur < sz(val));
		val[cur] = 0;
		if (l == r) return cur;
		int mid = (l + r) >> 1;
		idL[cur] = build(l, mid);
		idR[cur] = build(mid + 1, r);
		return cur;
	}
	int update(int i, int v, int oID, int l = 1, int r = n) {
		int cur = ++no;
		assert(cur < sz(val));
		if (l == r) {
			val[cur] = val[oID] + v;
			return cur;
		}
		int mid = (l + r) >> 1;
		if (i <= mid) {
			idL[cur] = update(i, v, idL[oID], l, mid);
			idR[cur] = idR[oID];
		} else {
			idL[cur] = idL[oID];
			idR[cur] = update(i, v, idR[oID], mid + 1, r);
		}
		val[cur] = val[idL[cur]] + val[idR[cur]];
		return cur;
	}
	int get(int Lf, int Rt, int id, int l = 1, int r = n) {
	    assert(1 <= Lf && Rt <= n);
		if (Lf <= l && r <= Rt) {
			return val[id];
		}
		int mid = (l + r) >> 1;
		int res = 0;
		if (Lf <= mid) res += get(Lf, Rt, idL[id], l, mid);
		if (Rt > mid) res += get(Lf, Rt, idR[id], mid + 1, r);
		return res;
	}
} T[4];
int root[4][MXn];
 
bool onboard(int x, int y) {
	return 1 <= x && x <= n && 1 <= y && y <= m;
}
vector<int> river[MXn], v1[MXn], v2[MXn], v3[MXn];
void add(int sr, int sc) {
    assert(onboard(sr, sc));
	river[sc].emplace_back(sr);
	if (sc > 1) v1[sc - 1].emplace_back(sr);
	v1[sc].emplace_back(sr);
	if (sr > 1) v2[sc].emplace_back(sr - 1);
	v2[sc].emplace_back(sr);
	v3[sc].emplace_back(sr);
	for (int k = 0; k < 3; k++) {
		int xx = dx[k] + sr, yy = dy[k] + sc;
		if (onboard(xx, yy)) v3[yy].emplace_back(xx);
	}
}
void init(int R, int C, int sr, int sc, int M, char *S) {
	n = R, m = C;
	add(sr, sc);
	for (int i = 0; i < M; i++) {
		if (S[i] == 'N') sr--;
		if (S[i] == 'S') sr++;
		if (S[i] == 'W') sc--;
		if (S[i] == 'E') sc++;
		add(sr, sc);
	}
	vector<int> siz(4, 0);
	for (int c = 1; c <= C; c++) {
		sort(begin(river[c]), end(river[c]));
		river[c].resize(unique(begin(river[c]), end(river[c])) - river[c].begin());
		siz[0] += sz(river[c]);
		sort(begin(v1[c]), end(v1[c]));
		v1[c].resize(unique(begin(v1[c]), end(v1[c])) - v1[c].begin());
		siz[1] += sz(v1[c]);
		sort(begin(v2[c]), end(v2[c]));
		v2[c].resize(unique(begin(v2[c]), end(v2[c])) - v2[c].begin());
		siz[2] += sz(v2[c]);
		sort(begin(v3[c]), end(v3[c]));
		v3[c].resize(unique(begin(v3[c]), end(v3[c])) - v3[c].begin());
		siz[3] += sz(v3[c]);
	}
	for (int t = 0; t < 4; t++) {
		T[t].resiz((1 << 19) + siz[t] * 19);
		root[t][0] = T[t].build();
	}
	for (int c = 1; c <= C; c++) {
		root[0][c] = root[0][c - 1];
		root[1][c] = root[1][c - 1];
		root[2][c] = root[2][c - 1];
		root[3][c] = root[3][c - 1];
		
		for (int r: river[c]) {
			root[0][c] = T[0].update(r, 1, root[0][c]);
		}
		for (int r: v1[c]) {
			root[1][c] = T[1].update(r, 1, root[1][c]);
		}
		for (int r: v2[c]) {
			root[2][c] = T[2].update(r, 1, root[2][c]);
		}
		for (int r: v3[c]) {
			root[3][c] = T[3].update(r, 1, root[3][c]);
		}
	}
}
 
int colour(int ar, int ac, int br, int bc) {
	long long V = (br - ar + 1) * (bc - ac + 1) - (T[0].get(ar, br, root[0][bc]) - T[0].get(ar, br, root[0][ac - 1]));
	long long E = (bc - ac) * (br - ar + 1) - (T[1].get(ar, br, root[1][bc - 1]) - T[1].get(ar, br, root[1][ac - 1])) + (bc - ac + 1) * (br - ar);
 	long long F = 0;
 	if (ar < br) {
 	    E -= (T[2].get(ar, br - 1, root[2][bc]) - T[2].get(ar, br - 1, root[2][ac - 1]));
 	    F = (br - ar) * (bc - ac) - (T[3].get(ar + 1, br, root[3][bc]) - T[3].get(ar + 1, br, root[3][ac]));
 	}
 	return V - E + F;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 45912 KB Output is correct
2 Correct 16 ms 46684 KB Output is correct
3 Incorrect 16 ms 45912 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 15 ms 45660 KB Output is correct
2 Correct 14 ms 45692 KB Output is correct
3 Correct 96 ms 121688 KB Output is correct
4 Correct 130 ms 171088 KB Output is correct
5 Correct 124 ms 168788 KB Output is correct
6 Correct 110 ms 137300 KB Output is correct
7 Correct 105 ms 132692 KB Output is correct
8 Correct 72 ms 51488 KB Output is correct
9 Correct 126 ms 171340 KB Output is correct
10 Correct 123 ms 168716 KB Output is correct
11 Correct 112 ms 137168 KB Output is correct
12 Correct 107 ms 162984 KB Output is correct
13 Correct 112 ms 171216 KB Output is correct
14 Correct 112 ms 168652 KB Output is correct
15 Correct 102 ms 137300 KB Output is correct
16 Correct 111 ms 135136 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 45656 KB Output is correct
2 Correct 154 ms 193228 KB Output is correct
3 Correct 161 ms 184984 KB Output is correct
4 Correct 170 ms 187796 KB Output is correct
5 Correct 124 ms 153072 KB Output is correct
6 Correct 69 ms 76800 KB Output is correct
7 Incorrect 92 ms 102252 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 45912 KB Output is correct
2 Correct 16 ms 46684 KB Output is correct
3 Incorrect 16 ms 45912 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 45912 KB Output is correct
2 Correct 16 ms 46684 KB Output is correct
3 Incorrect 16 ms 45912 KB Output isn't correct
4 Halted 0 ms 0 KB -