oj.uz

Submission #676921

# Submission time Handle Problem Language Result Execution time Memory
676921 2023-01-01T15:12:41 Z kingfran1907 Land of the Rainbow Gold (APIO17_rainbow) C++14
12 / 100
 876 ms 411332 KB 
#include "rainbow.h"
#include <bits/stdc++.h>
#define X first
#define Y second

using namespace std;
typedef long long llint;

const int maxn = 2e5+10;
const int logo = 19;
const int off = 1 << logo;
const int treesiz = off << 1;

struct node {
	node *l, *r;
	int val;
	node() {
		l = r = nullptr;
		val = 0;
	}
};
typedef node* pnode;

inline pnode L(pnode tren) {
	if (tren == nullptr) return nullptr;
	return tren->l;
}

inline pnode R(pnode tren) {
	if (tren == nullptr) return nullptr;
	return tren->r;
}

inline int value(pnode tren) {
	if (tren == nullptr) return 0;
	return tren->val;
}

void update(pnode tren, pnode prev, int x, int l, int r, int val) {
	if (l > x || r < x) return;
	if (x == l && x == r) {
		tren->val = value(prev) + val;
		return;
	}

	int mid = (l + r) / 2;
	if (x <= mid) {
		tren->l = new node();
		tren->r = R(prev);
		update(tren->l, L(prev), x, l, mid, val);
	} else {
		tren->r = new node();
		tren->l = L(prev);
		update(tren->r, R(prev), x, mid + 1, r, val);
	}
	tren->val = value(tren->l) + value(tren->r);
}

int query(pnode tren, int a, int b, int l, int r) {
	if (tren == nullptr) return 0;
	if (l > b || r < a) return 0;
	if (l >= a && r <= b) return tren->val;
	
	int mid = (l + r) / 2;
	return query(tren->l, a, b, l, mid) + query(tren->r, a, b, mid + 1, r);
}

struct tournament {
	pnode root[maxn];
	int kol;
	tournament() {
		kol = 0;
		for (int i = 0; i < maxn; i++) 
			root[i] = nullptr;
	}
	
	void add(vector< int > &v) {
		pnode ptr = root[kol];
		kol++;
		for (int tren : v) {
			pnode nw = new node();
			update(nw, ptr, tren, 0, off - 1, 1);
			ptr = nw;
		}
		root[kol] = ptr;
	}
	
	int query(int x1, int y1, int x2, int y2) {
		if (x1 > x2 || y1 > y2) return 0;
		return ::query(root[x2], y1, y2, 0, off - 1) - ::query(root[x1 - 1], y1, y2, 0, off - 1);
	}
} vert, faces, edgesx, edgesy;

void insert(set< pair<int, int> > &s, tournament &tour) {
	auto iter = s.begin();
	for (int i = 1; i < maxn; i++) {
		vector< int > v;
		while (iter != s.end() && iter->X == i) {
			v.push_back(iter->Y);
			iter++;
		}
		tour.add(v);
	}
}

void init(int R, int C, int sr, int sc, int M, char *S) {
	set< pair<int, int> > s;
	s.insert({sr, sc});
	for (int i = 0; i < M; i++) {
		if (S[i] == 'N') sr--;
		else if (S[i] == 'S') sr++;
		else if (S[i] == 'W') sc--;
		else sc++;
		s.insert({sr, sc});
	}
	
	auto iter = s.begin();
	set< pair<int, int> > ac;
	set< pair<int, int> > xv, yv;
	for (int i = 1; i < maxn; i++) {
		vector< int > v;
		while (iter != s.end() && iter->X == i) {
			for (int x = 0; x < 2; x++)
				for (int y = 0; y < 2; y++)
					ac.insert({iter->X + x, iter->Y + y});
			xv.insert(*iter); xv.insert({iter->X + 1, iter->Y});
			yv.insert(*iter); yv.insert({iter->X, iter->Y + 1});
			
			v.push_back(iter->Y);
			iter++;
		}
		vert.add(v);
	}
	insert(ac, faces);
	insert(xv, edgesx);
	insert(yv, edgesy);
}

int colour(int ar, int ac, int br, int bc) {
	llint v = (llint)(br - ar + 1) * (bc - ac + 1) - vert.query(ar, ac, br, bc);
	llint f = (llint)(br - ar) * (bc - ac) - faces.query(ar + 1, ac + 1, br, bc);
	llint e = (llint)(br - ar + 1) * (bc - ac) + (llint)(br - ar) * (bc - ac + 1);
	e -= edgesx.query(ar + 1, ac, br, bc);
	e -= edgesy.query(ar, ac + 1, br, bc);
	
	//printf("debug: %lld %lld %lld\n", v, e, f);
	assert(v + f - e >= 0);
   	return v + f - e;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7200 KB Output is correct
2 Correct 13 ms 9812 KB Output is correct
3 Incorrect 9 ms 7252 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 7 ms 6556 KB Output is correct
2 Correct 7 ms 6484 KB Output is correct
3 Correct 520 ms 248196 KB Output is correct
4 Correct 832 ms 411332 KB Output is correct
5 Correct 850 ms 407952 KB Output is correct
6 Correct 623 ms 316008 KB Output is correct
7 Correct 730 ms 310448 KB Output is correct
8 Correct 68 ms 7300 KB Output is correct
9 Correct 845 ms 411116 KB Output is correct
10 Correct 876 ms 407880 KB Output is correct
11 Correct 651 ms 315656 KB Output is correct
12 Correct 635 ms 382844 KB Output is correct
13 Correct 672 ms 411092 KB Output is correct
14 Correct 690 ms 407920 KB Output is correct
15 Correct 572 ms 316272 KB Output is correct
16 Correct 609 ms 292592 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6484 KB Output is correct
2 Correct 667 ms 410904 KB Output is correct
3 Correct 716 ms 410452 KB Output is correct
4 Correct 708 ms 410588 KB Output is correct
5 Correct 519 ms 309492 KB Output is correct
6 Correct 132 ms 82168 KB Output is correct
7 Incorrect 250 ms 157404 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7200 KB Output is correct
2 Correct 13 ms 9812 KB Output is correct
3 Incorrect 9 ms 7252 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7200 KB Output is correct
2 Correct 13 ms 9812 KB Output is correct
3 Incorrect 9 ms 7252 KB Output isn't correct
4 Halted 0 ms 0 KB -