oj.uz

Submission #214019

# Submission time Handle Problem Language Result Execution time Memory
214019 2020-03-26T10:25:09 Z spdskatr Land of the Rainbow Gold (APIO17_rainbow) C++14
12 / 100
 805 ms 197112 KB 
#include "rainbow.h"
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <utility>
#include <vector>
#include <set>
#define fi first
#define se second

using namespace std;
typedef pair<int, int> pii;

class PersistentSegtree {
public:
	int st[10000000], lc[10000000], rc[10000000], cnt = 1;
	int heads[200005];
	void seg_inc(int n, int pn, int lo, int hi, int i, int v) {
		if (lo + 1 == hi) {
			st[n] = st[pn] + v;
			return;
		}
		lc[n] = lc[pn], rc[n] = rc[pn];
		int mid = (lo + hi) / 2;
		if (mid > i) {
			lc[n] = cnt++;
			seg_inc(lc[n], lc[pn], lo, mid, i, v);
		} else {
			rc[n] = cnt++;
			seg_inc(rc[n], rc[pn], mid, hi, i, v);
		}
		st[n] = st[lc[n]] + st[rc[n]];
	}
	int seg_sum(int n, int pn, int lo, int hi, int l, int r) {
		if (lo >= r || hi <= l) return 0;
		if (lo >= l && hi <= r) {
			return st[n] - st[pn];
		}
		int mid = (lo + hi) / 2;
		return seg_sum(lc[n], lc[pn], lo, mid, l, r) + seg_sum(rc[n], rc[pn], mid, hi, l, r);
	}
} st[4];
vector<int> rec[4][200005];
set<pii> water, vedges, hedges, verts;

void init(int R, int C, int sr, int sc, int M, char *S) {
	water.insert({ sr, sc });
	for (int i = 0; i < M; i++) {
		if (S[i] == 'N') {
			sr -= 1;
		} else if (S[i] == 'S') {
			sr += 1;
		} else if (S[i] == 'E') {
			sc += 1;
		} else {
			sc -= 1;
		}
		water.insert({ sr, sc });
	}
	for (pii p : water) {
		verts.insert(p);
		verts.insert({ p.fi + 1, p.se });
		verts.insert({ p.fi, p.se + 1 });
		verts.insert({ p.fi + 1, p.se + 1 });
		vedges.insert(p);
		vedges.insert({ p.fi, p.se + 1 });
		hedges.insert(p);
		hedges.insert({ p.fi + 1, p.se });
		rec[0][p.fi].push_back(p.se);
	}
	for (pii p : verts) rec[1][p.fi].push_back(p.se);
	for (pii p : hedges) rec[2][p.fi].push_back(p.se);
	for (pii p : vedges) rec[3][p.fi].push_back(p.se);
	for (int j = 0; j < 4; j++) {
		for (int i = 1; i <= R; i++) {
			int node = st[j].heads[i-1];
			for (int x : rec[j][i]) {
				int nn = st[j].cnt++;
				st[j].seg_inc(nn, node, 1, 200005, x, 1);
				node = nn;
			}
			st[j].heads[i] = node;
		}
	}
}

int colour(int ar, int ac, int br, int bc) {
	int a = st[3].seg_sum(st[3].heads[br], st[3].heads[ar-1], 1, 200005, ac + 1, bc + 1);
	int b = st[2].seg_sum(st[2].heads[br], st[2].heads[ar], 1, 200005, ac, bc + 1);
	int c = st[1].seg_sum(st[1].heads[br], st[1].heads[ar], 1, 200005, ac + 1, bc + 1);
	int d = st[0].seg_sum(st[0].heads[br], st[0].heads[ar-1], 1, 200005, ac, bc + 1);
    return 1 + a + b - c - d;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 19712 KB Output is correct
2 Correct 19 ms 20608 KB Output is correct
3 Incorrect 18 ms 19584 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 19200 KB Output is correct
2 Correct 18 ms 19200 KB Output is correct
3 Correct 519 ms 105344 KB Output is correct
4 Correct 729 ms 163184 KB Output is correct
5 Correct 722 ms 161392 KB Output is correct
6 Correct 577 ms 127348 KB Output is correct
7 Correct 805 ms 128372 KB Output is correct
8 Correct 255 ms 22916 KB Output is correct
9 Correct 753 ms 163824 KB Output is correct
10 Correct 730 ms 161648 KB Output is correct
11 Correct 573 ms 127220 KB Output is correct
12 Correct 448 ms 149100 KB Output is correct
13 Correct 459 ms 163188 KB Output is correct
14 Correct 512 ms 161084 KB Output is correct
15 Correct 413 ms 127348 KB Output is correct
16 Correct 594 ms 127732 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 19200 KB Output is correct
2 Correct 422 ms 184944 KB Output is correct
3 Correct 402 ms 197112 KB Output is correct
4 Correct 427 ms 188664 KB Output is correct
5 Correct 293 ms 150364 KB Output is correct
6 Correct 94 ms 53112 KB Output is correct
7 Incorrect 155 ms 83576 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 19712 KB Output is correct
2 Correct 19 ms 20608 KB Output is correct
3 Incorrect 18 ms 19584 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 19712 KB Output is correct
2 Correct 19 ms 20608 KB Output is correct
3 Incorrect 18 ms 19584 KB Output isn't correct
4 Halted 0 ms 0 KB -