oj.uz

Submission #676910

# Submission time Handle Problem Language Result Execution time Memory
676910 2023-01-01T14:40:43 Z kingfran1907 Land of the Rainbow Gold (APIO17_rainbow) C++14
12 / 100
 1014 ms 414256 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;
};
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) {
		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 15 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 6484 KB Output is correct
2 Correct 7 ms 6484 KB Output is correct
3 Correct 607 ms 251224 KB Output is correct
4 Correct 968 ms 414236 KB Output is correct
5 Correct 957 ms 411148 KB Output is correct
6 Correct 694 ms 318872 KB Output is correct
7 Correct 839 ms 313800 KB Output is correct
8 Correct 88 ms 10328 KB Output is correct
9 Correct 1010 ms 414256 KB Output is correct
10 Correct 1014 ms 410984 KB Output is correct
11 Correct 728 ms 318684 KB Output is correct
12 Correct 724 ms 385888 KB Output is correct
13 Correct 757 ms 414132 KB Output is correct
14 Correct 809 ms 411032 KB Output is correct
15 Correct 641 ms 319132 KB Output is correct
16 Correct 693 ms 295544 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 689 ms 411364 KB Output is correct
3 Correct 744 ms 410676 KB Output is correct
4 Correct 699 ms 410592 KB Output is correct
5 Correct 541 ms 309596 KB Output is correct
6 Correct 134 ms 82228 KB Output is correct
7 Incorrect 282 ms 157516 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 15 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 7124 KB Output is correct
2 Correct 15 ms 9812 KB Output is correct
3 Incorrect 9 ms 7252 KB Output isn't correct
4 Halted 0 ms 0 KB -