oj.uz

Submission #885416

# Submission time Handle Problem Language Result Execution time Memory
885416 2023-12-09T15:48:32 Z pubin06 Land of the Rainbow Gold (APIO17_rainbow) C++14
12 / 100
 165 ms 193384 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]));
 	}
//    if (ar == 2) return 0;
//    if (ar == 3) return 2;
//    if (ar == 5) return 1;
//    if (ar == 1) return 3;
 	return V - E + F;
//    return V - E;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 45916 KB Output is correct
2 Correct 17 ms 46940 KB Output is correct
3 Incorrect 20 ms 46220 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 14 ms 45660 KB Output is correct
2 Correct 15 ms 45660 KB Output is correct
3 Correct 102 ms 124496 KB Output is correct
4 Correct 131 ms 174164 KB Output is correct
5 Correct 131 ms 171632 KB Output is correct
6 Correct 111 ms 140068 KB Output is correct
7 Correct 107 ms 135764 KB Output is correct
8 Correct 74 ms 54308 KB Output is correct
9 Correct 123 ms 174164 KB Output is correct
10 Correct 125 ms 171604 KB Output is correct
11 Correct 111 ms 140236 KB Output is correct
12 Correct 106 ms 165712 KB Output is correct
13 Correct 114 ms 174020 KB Output is correct
14 Correct 112 ms 171600 KB Output is correct
15 Correct 104 ms 140112 KB Output is correct
16 Correct 117 ms 138320 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 156 ms 193384 KB Output is correct
3 Correct 160 ms 184848 KB Output is correct
4 Correct 165 ms 188356 KB Output is correct
5 Correct 123 ms 153220 KB Output is correct
6 Correct 67 ms 76876 KB Output is correct
7 Incorrect 88 ms 102224 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 45916 KB Output is correct
2 Correct 17 ms 46940 KB Output is correct
3 Incorrect 20 ms 46220 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 45916 KB Output is correct
2 Correct 17 ms 46940 KB Output is correct
3 Incorrect 20 ms 46220 KB Output isn't correct
4 Halted 0 ms 0 KB -