oj.uz

Submission #160725

# Submission time Handle Problem Language Result Execution time Memory
160725 2019-10-29T14:08:13 Z songc Land of the Rainbow Gold (APIO17_rainbow) C++14
0 / 100
 319 ms 198136 KB 
#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;

int N, R, C;
set<pii> P;

struct Node{
	int val=0;
	int lc=0, rc=0;
};

struct PST{
	int rt[202020], cnt=1;
	Node T[4040404];

	void update(int pre, int now, int s, int e, int t){
		if (pre != now) T[now].val = T[pre].val;
		T[now].val++;
		if (s == e) return;
		int mid = (s+e)/2;
		if (t <= mid){
			if (!T[now].lc) {
				T[now].lc = cnt++;
				T[now].rc = T[pre].rc;
			}
			update(T[pre].lc, T[now].lc, s, mid, t);
		}
		else{
			if (!T[now].rc) {
				T[now].rc = cnt++;
				T[now].lc = T[pre].lc;
			}
			update(T[pre].rc, T[now].rc, mid+1, e, t);
		}
	}

	int query(int now, int s, int e, int ts, int te){
		if (e < ts || te < s || T[now].val == 0) return 0;
		if (ts <= s && e <= te) return T[now].val;
		int mid = (s+e)/2;
		return query(T[now].lc, s, mid, ts, te)+query(T[now].rc, mid+1, e, ts, te);
	}
} V, HE, VE, F;


void init(int _R, int _C, int sr, int sc, int _M, char *S) {
	R = _R, C = _C, N = _M;
	P.insert(pii(sr, sc));
	for (int i=0; i<N; i++){
		if (S[i] == 'N') sr--;
		if (S[i] == 'S') sr++;
		if (S[i] == 'W') sc--;
		if (S[i] == 'E') sc++;
		P.insert(pii(sr, sc));
	}
	int lr=0;
	for (pii it : P){
		for (int i=lr+1; i<it.first; i++){
			V.rt[it.first] = V.rt[lr]; 
			HE.rt[it.first] = HE.rt[lr]; 
			VE.rt[it.first] = VE.rt[lr]; 
			F.rt[it.first] = F.rt[lr]; 
		}

		if (!V.rt[it.first]) {
			V.rt[it.first] = V.cnt++;
			V.update(V.rt[it.first-1], V.rt[it.first], 1, C, it.second);
		}
		else V.update(V.rt[it.first], V.rt[it.first], 1, C, it.second);
		
		if (P.find(pii(it.first, it.second+1)) != P.end()){
			if (!HE.rt[it.first]) {
				HE.rt[it.first] = HE.cnt++;
				HE.update(HE.rt[it.first-1], HE.rt[it.first], 1, C, it.second);
			}
			else HE.update(HE.rt[it.first], HE.rt[it.first], 1, C, it.second);
		}
		else if (!HE.rt[it.first]) HE.rt[it.first] = HE.rt[it.first-1];

		if (P.find(pii(it.first+1, it.second)) != P.end()){
			if (!VE.rt[it.first]) {
				VE.rt[it.first] = VE.cnt++;
				VE.update(VE.rt[it.first-1], VE.rt[it.first], 1, C, it.second);
			}
			else VE.update(VE.rt[it.first], VE.rt[it.first], 1, C, it.second);
		}
		else if (!VE.rt[it.first]) VE.rt[it.first] = VE.rt[it.first-1];

		if (P.find(pii(it.first+1, it.second+1)) != P.end()
			&& P.find(pii(it.first, it.second+1)) != P.end()
			&& P.find(pii(it.first+1, it.second)) != P.end()){
			if (!F.rt[it.first]) {
				F.rt[it.first] = F.cnt++;
				F.update(F.rt[it.first-1], F.rt[it.first], 1, C, it.second);
			}
			else F.update(F.rt[it.first], F.rt[it.first], 1, C, it.second);
		}
		else if (!F.rt[it.first]) F.rt[it.first] = F.rt[it.first-1];

		lr = it.first;
	}
	for (int i=lr+1; i<=R; i++){
		V.rt[i] = V.rt[lr];
		HE.rt[i] = HE.rt[lr];
		VE.rt[i] = VE.rt[lr];
		F.rt[i] = F.rt[lr];
	}
}

int colour(int ar, int ac, int br, int bc) {
	int ret = 1;
	if (ar < br) ret += HE.query(HE.rt[br-1], 1, C, ac, bc-1) - HE.query(HE.rt[ar], 1, C, ac, bc-1);
	ret += VE.query(VE.rt[br-1], 1, C, ac+1, bc-1) - VE.query(VE.rt[ar-1], 1, C, ac+1, bc-1);
	
	ret += V.query(V.rt[ar], 1, C, ac, bc) - V.query(V.rt[ar-1], 1, C, ac, bc);
	ret += V.query(V.rt[br], 1, C, ac, bc) - V.query(V.rt[br-1], 1, C, ac, bc);
	ret += V.query(V.rt[br], 1, C, ac, ac) - V.query(V.rt[ar-1], 1, C, ac, ac);
	ret += V.query(V.rt[br], 1, C, bc, bc) - V.query(V.rt[ar-1], 1, C, bc, bc);
    
    ret -= V.query(V.rt[br], 1, C, ac, bc) - V.query(V.rt[ar-1], 1, C, ac, bc);
    ret -= F.query(F.rt[br-1], 1, C, ac, bc-1) - F.query(F.rt[ar-1], 1, C, ac, bc-1);
    if (P.find(pii(ar, ac)) != P.end()) ret--;
    if (P.find(pii(ar, bc)) != P.end()) ret--;
    if (P.find(pii(br, ac)) != P.end()) ret--;
    if (P.find(pii(br, bc)) != P.end()) ret--;
    return ret;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 163 ms 190200 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 161 ms 190152 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 190116 KB Output is correct
2 Correct 319 ms 196532 KB Output is correct
3 Correct 256 ms 197584 KB Output is correct
4 Correct 280 ms 198136 KB Output is correct
5 Correct 233 ms 196240 KB Output is correct
6 Correct 186 ms 192504 KB Output is correct
7 Incorrect 214 ms 194040 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 163 ms 190200 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 163 ms 190200 KB Output isn't correct
2 Halted 0 ms 0 KB -