Submission #620049

#	Time	Username	Problem	Language	Result	Execution time	Memory
620049		penguinhacker	Land of the Rainbow Gold (APIO17_rainbow)	C++17	100 / 100	1037 ms	406680 KiB

rainbow

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

const int mxN=2e5, INF=69696969;
int n, m, lr=INF, rr=-1, lc=INF, rc=-1;
set<int> vis[mxN];
vector<int> row_edge[mxN], col_edge[mxN], faces[mxN];

bool ok(int i, int j) {
	return 0<=i&&i<n&&0<=j&&j<m&&vis[i].find(j)==vis[i].end();
}

void consider(int i, int j) {
	if (vis[i].find(j)==vis[i].end()) {
		lr=min(lr, i), rr=max(rr, i);
		lc=min(lc, j), rc=max(rc, j);
		if (ok(i, j-1))  row_edge[i].push_back(j-1);
		if (ok(i, j+1)) row_edge[i].push_back(j);
		if (ok(i-1, j)) col_edge[i-1].push_back(j);
		if (ok(i+1, j)) col_edge[i].push_back(j);
		for (int a : {i-1, i})
			for (int b : {j-1, j})
				if (ok(a, b)&&ok(a+1, b)&&ok(a, b+1)&&ok(a+1, b+1))
					faces[a].push_back(b);
		vis[i].insert(j);
	}
}

struct Node {
	int s=0;
	Node *left=nullptr, *right=nullptr;
	Node(int l, int r) {
		if (l!=r) {
			int mid=(l+r)/2;
			left=new Node(l, mid);
			right=new Node(mid+1, r);
		}
	}
	Node(int x) : s(x) {}
	Node(Node* left, Node* right) : left(left), right(right) { s=left->s+right->s; }
	Node* upd(int i, int l, int r) {
		if (l>i||r<i) return this;
		if (l==r) return new Node(s+1);
		int mid=(l+r)/2;
		return new Node(left->upd(i, l, mid), right->upd(i, mid+1, r));
	}
	int qry(int ql, int qr, int l, int r) {
		if (l>qr||r<ql) return 0;
		if (ql<=l&&r<=qr) return s;
		int mid=(l+r)/2;
		return left->qry(ql, qr, l, mid)+right->qry(ql, qr, mid+1, r);
	}
};
vector<Node*> pv, pre, pce, pf; // prefix vertex, prefix row edge, prefix column edge, prefix face

void init(int R, int C, int sr, int sc, int M, char *S) {
	n=R, m=C, --sr, --sc;
	consider(sr, sc);
	for (int i=0; i<M; ++i) {
		if (S[i]=='N'||S[i]=='S') sr+=S[i]=='S'?1:-1;
		else sc+=S[i]=='E'?1:-1;
		assert(0<=sr&&sr<n&&0<=sc&&sc<m);
		consider(sr, sc);
	}
	Node* cur=new Node(0, m-1);
	pv.push_back(cur);
	pre.push_back(cur);
	pce.push_back(cur);
	pf.push_back(cur);
	for (int i=0; i<n; ++i) {
		cur=pv.back();
		for (int j : vis[i]) cur=cur->upd(j, 0, m-1);
		pv.push_back(cur);
		
		cur=pre.back();
		for (int j : row_edge[i]) cur=cur->upd(j, 0, m-1);
		pre.push_back(cur);
		
		cur=pce.back();
		for (int j : col_edge[i]) cur=cur->upd(j, 0, m-1);
		pce.push_back(cur);

		cur=pf.back();
		for (int j : faces[i]) cur=cur->upd(j, 0, m-1);
		pf.push_back(cur);
	}
}

int cnt(vector<Node*>& p, int a, int b, int c, int d) {
	return p[c+1]->qry(b, d, 0, m-1)-p[a]->qry(b, d, 0, m-1);
}

int colour(int ar, int ac, int br, int bc) {
	--ar, --ac, --br, --bc;
	ll v=(ll)(br-ar+1)*(bc-ac+1)-cnt(pv, ar, ac, br, bc);
	ll e=(ll)(br-ar+1)*(bc-ac)+(ll)(br-ar)*(bc-ac+1)-cnt(pre, ar, ac, br, bc-1)-cnt(pce, ar, ac, br-1, bc);
	ll f=(ll)(br-ar)*(bc-ac)-cnt(pf, ar, ac, br-1, bc-1)+(ar<lr&&rr<br&&ac<lc&&rc<bc);
	return v-e+f;
}

/*int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	init(6, 4, 3, 3, 9, "NWESSWEWS");
	cout << colour(2, 3, 2, 3) << " " << colour(3, 2, 4, 4) << " " << colour(5, 3, 6, 4) << " " << colour(1, 2, 5, 3) << endl;
	return 0;
}*/

• Subtask 1: 11 / 11
• Subtask 2: 12 / 12
• Subtask 3: 24 / 24
• Subtask 4: 27 / 27
• Subtask 5: 26 / 26