oj.uz

Submission #524207

# Submission time Handle Problem Language Result Execution time Memory
524207 2022-02-08T19:28:53 Z sidon Land of the Rainbow Gold (APIO17_rainbow) C++17
12 / 100
 862 ms 114768 KB 
#include <bits/stdc++.h>
using namespace std;
#define all(X) begin(X), end(X)

const int Z = 2e5+4;

template<const int n>
struct SegmentTree {
	vector<int> a[2*n];
	void insert(int i, int v) {
		a[i+n].push_back(v);
	}
	void build() {
		for(int i = n; i < 2*n; ++i) {
			sort(all(a[i]));
			a[i].erase(unique(all(a[i])), end(a[i]));
		}
		for(int i = n; --i; )
			merge(all(a[2*i]), all(a[2*i+1]), back_inserter(a[i]));
	}
	int getCnt(int i, int lv, int rv) {
		return upper_bound(all(a[i]), rv) - lower_bound(all(a[i]), lv);
	}
	int count(int l, int r, int lv, int rv) {
		int x = 0;
		for(l += n, r += n+1; l < r; l /= 2, r /= 2) {
			if(l & 1) x += getCnt(l++, lv, rv);
			if(r & 1) x += getCnt(--r, lv, rv);
		}
		return x;
	}
};

SegmentTree<2*Z> edges;
SegmentTree<Z> cells, vertices;

void init(int R, int C, int uR, int uC, int M, char* S) {
	for(int i = 0; i <= M; ++i) {
		cells.insert(uC, uR);
		for(int x : {0, 1}) for(int y : {0, 1}) {
			vertices.insert(uC+x, uR+y);
		}
		for(int x : {0, 2}) {
			edges.insert(2*uC+x, 2*uR+1);
			edges.insert(2*uC+1, 2*uR+x);
		}
		if(i < M) {
			S[i] == 'S' ? ++uR : 0;
			S[i] == 'N' ? --uR : 0;
			S[i] == 'E' ? ++uC : 0;
			S[i] == 'W' ? --uC : 0;
		}
	}
	edges.build();
	cells.build();
	vertices.build();
}

int colour(int ar, int ac, int br, int bc) {
	return edges.count(2*ac+1, 2*bc+1, 2*ar+1, 2*br+1) - vertices.count(ac+1, bc, ar+1, br) - cells.count(ac, bc, ar, br) + 1;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 37904 KB Output is correct
2 Correct 31 ms 38456 KB Output is correct
3 Incorrect 28 ms 37996 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 30 ms 37872 KB Output is correct
2 Correct 27 ms 37836 KB Output is correct
3 Correct 491 ms 81208 KB Output is correct
4 Correct 799 ms 114696 KB Output is correct
5 Correct 733 ms 113100 KB Output is correct
6 Correct 492 ms 94480 KB Output is correct
7 Correct 674 ms 93856 KB Output is correct
8 Correct 201 ms 46124 KB Output is correct
9 Correct 862 ms 114768 KB Output is correct
10 Correct 777 ms 113324 KB Output is correct
11 Correct 554 ms 94616 KB Output is correct
12 Correct 316 ms 104292 KB Output is correct
13 Correct 339 ms 114568 KB Output is correct
14 Correct 357 ms 113164 KB Output is correct
15 Correct 311 ms 94700 KB Output is correct
16 Correct 528 ms 89340 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 37856 KB Output is correct
2 Correct 189 ms 106784 KB Output is correct
3 Correct 109 ms 86760 KB Output is correct
4 Correct 144 ms 94772 KB Output is correct
5 Correct 120 ms 80540 KB Output is correct
6 Correct 76 ms 52084 KB Output is correct
7 Incorrect 94 ms 61504 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 37904 KB Output is correct
2 Correct 31 ms 38456 KB Output is correct
3 Incorrect 28 ms 37996 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 37904 KB Output is correct
2 Correct 31 ms 38456 KB Output is correct
3 Incorrect 28 ms 37996 KB Output isn't correct
4 Halted 0 ms 0 KB -