oj.uz

Submission #676920

# Submission time Handle Problem Language Result Execution time Memory
676920 2023-01-01T15:11:55 Z kingfran1907 Land of the Rainbow Gold (APIO17_rainbow) C++14
12 / 100
 856 ms 411520 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);
   	return v + f - e;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7124 KB Output is correct
2 Correct 13 ms 9812 KB Output is correct
3 Incorrect 9 ms 7296 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 6616 KB Output is correct
2 Correct 7 ms 6484 KB Output is correct
3 Correct 516 ms 248564 KB Output is correct
4 Correct 811 ms 411520 KB Output is correct
5 Correct 833 ms 408360 KB Output is correct
6 Correct 611 ms 316064 KB Output is correct
7 Correct 732 ms 310668 KB Output is correct
8 Correct 70 ms 7496 KB Output is correct
9 Correct 838 ms 411376 KB Output is correct
10 Correct 856 ms 408264 KB Output is correct
11 Correct 641 ms 316008 KB Output is correct
12 Correct 629 ms 382744 KB Output is correct
13 Correct 668 ms 411060 KB Output is correct
14 Correct 715 ms 407980 KB Output is correct
15 Correct 544 ms 316208 KB Output is correct
16 Correct 583 ms 292596 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6568 KB Output is correct
2 Correct 640 ms 410972 KB Output is correct
3 Correct 695 ms 410712 KB Output is correct
4 Correct 677 ms 410644 KB Output is correct
5 Correct 509 ms 309804 KB Output is correct
6 Correct 128 ms 82180 KB Output is correct
7 Incorrect 256 ms 157336 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 7124 KB Output is correct
2 Correct 13 ms 9812 KB Output is correct
3 Incorrect 9 ms 7296 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 7124 KB Output is correct
2 Correct 13 ms 9812 KB Output is correct
3 Incorrect 9 ms 7296 KB Output isn't correct
4 Halted 0 ms 0 KB -