Submission #885372

#	Time	Username	Problem	Language	Result	Execution time	Memory
885372		pubin06	Land of the Rainbow Gold (APIO17_rainbow)	C++14	0 / 100	725 ms	1048576 KiB

rainbow

#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);
		idL.resize(s + 3);
		idR.resize(s + 3);
	}
	int no = 0;
	int build(int l = 1, int r = n) {
		int cur = ++no;
		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) {
		// if (l == 1 && r == m) cerr << i << ' ' << v << '\n';
		int nod = ++no;
		if (l == r) {
			val[nod] = val[oID] + v;
			return nod;
		}
		int mid = (l + r) >> 1;
		if (i <= mid) {
			idL[nod] = update(i, v, idL[oID], l, mid);
			idR[nod] = idR[oID];
		} else {
			idL[nod] = idL[oID];
			idR[nod] = update(i, v, idR[oID], mid + 1, r);
		}
		val[nod] = val[idL[nod]] + val[idR[nod]];
		return nod;
	}
	int get(int Lf, int Rt, int id, int l = 1, int r = n) {
		if (Lf <= l && r <= Rt) {
			// cerr << id << ' ' << l << ' ' << r << ' ' << val[id] << '\n';
			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) {
	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++;
		// cerr << "(" << sr << ' ' << sc << ")\n";
		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]);
	}
	// cerr << '\n';
	// T[0].resize((1 << 19) + sz[0] * 19);
	// T[1].resize((1 << 19) + sz[1] * 19);
	// T[2].resize((1 << 19) + sz[2] * 19);
	// T[3].resize((1 << 19) + sz[3] * 19);
	for (int t = 0; t < 4; t++) {
		T[t].resiz((1 << 19) + siz[t] * 19);
		root[t][0] = T[t].build();
	}
	// int ro = T[0].update(4, 1, root[0][0]);
	// cerr << T[0].get(3, 4, ro) << '\n';
	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]) {
			// cerr << r << ' ';
			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]);
		}
		// cerr << "---\n" << T[0].get(3, 4, root[0][c]) << '\n';
	}
	// cerr << '\n';
}

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) - (T[2].get(ar, br - 1, root[2][bc]) - T[2].get(ar, br - 1, root[2][ac - 1]));
	long long F = 0;
	if (ar < br) F = (br - ar) * (bc - ac) - (T[3].get(ar + 1, br, root[3][bc]) - T[3].get(ar + 1, br, root[3][ac]));
	// cerr << V << ' ' << E << ' ' << F << '\n';
	// cerr << V << ' ' << T[0].get(ar, br, root[0][bc]) << ' ' << T[0].get(ar, br, root[0][ac - 1]) << '\n';
	return V - E + F;
	// return 0;
}

// static int R, C, M, Q;
// static int sr, sc;
// static char S[100000 + 5];
// 
// int main() {
    // scanf("%d %d %d %d", &R, &C, &M, &Q);
    // scanf("%d %d", &sr, &sc);
    // if (M > 0) {
        // scanf(" %s ", S);
    // }
// 
    // init(R, C, sr, sc, M, S);
// 
    // int query;
    // for (query = 0; query < Q; query++) {
        // int ar, ac, br, bc;
        // scanf("%d %d %d %d", &ar, &ac, &br, &bc);
        // printf("%d\n", colour(ar, ac, br, bc));
    // }
// 
    // return 0;
// }

• Subtask 1: 0 / 11
• Subtask 2: 0 / 12
• Subtask 3: 0 / 24
• Subtask 4: 0 / 27
• Subtask 5: 0 / 26