Submission #115122

#	Time	Username	Problem	Language	Result	Execution time	Memory
115122		sebinkim	Land of the Rainbow Gold (APIO17_rainbow)	C++14	100 / 100	644 ms	214212 KiB

rainbow

#include <bits/stdc++.h>

#include "rainbow.h"

using namespace std;

typedef pair <int, int> pii;

struct pst{
	struct node{
		int l, r, v;
		node() : l(0), r(0), v(0) {}
	};
	
	node T[15151515];
	int R[202020], r, t, c;
	
	void init(int w) { c = w; }
	
	void insert(int p, int s, int e, int i, int v)
	{
		T[p].v += v;
		
		if(s == e) return;
		else if(i <= (s + e >> 1)){
			T[++t] = T[T[p].l]; T[p].l = t;
			insert(T[p].l, s, s + e >> 1, i, v);
		}
		else{
			T[++t] = T[T[p].r]; T[p].r = t;
			insert(T[p].r, (s + e >> 1) + 1, e, i, v);
		}
	}
	
	void insert(int p, int v)
	{
		T[++t] = T[r]; r = t;
		insert(r, 1, c, p, v);
	}
	
	void root(int p) { R[p] = r; }
	
	int query(int p, int s, int e, int l, int r)
	{
		if(!p || r < s || e < l) return 0;
		else if(l <= s && e <= r){
			return T[p].v;
		}
		else return query(T[p].l, s, s + e >> 1, l, r)
				+ query(T[p].r, (s + e >> 1) + 1, e, l, r);
	}
	
	int query(int sr, int sc, int er, int ec)
	{
		return query(R[er], 1, c, sc, ec) 
			- query(R[sr - 1], 1, c, sc, ec);	
	}
};

pst T;
vector <int> R1[202020], R2[202020];
vector <int> C1[202020], C2[202020];
vector <pii> V, E1, E2, F;
int lx, ly, rx, ry;

void push(int x, int y)
{
	V.emplace_back(x, y);
	
	E1.emplace_back(x, y);
	E1.emplace_back(x + 1, y);
	
	E2.emplace_back(x, y);
	E2.emplace_back(x, y + 1);
	
	F.emplace_back(x, y);
	F.emplace_back(x, y + 1);
	F.emplace_back(x + 1, y);
	F.emplace_back(x + 1, y + 1);
}

void compress(vector <pii> &V)
{
	sort(V.begin(), V.end());
	V.erase(unique(V.begin(), V.end()), V.end());
} 

void init(int r, int c, int x, int y, int m, char *S)
{
	int i, v, e1, e2, f;
	
	T.init(c + 1);
	
	push(x, y);
	
	lx = rx = x; ly = ry = y;
	
	for(i=0; i<m; i++){
		if(S[i] == 'N') x --;
		else if(S[i] == 'S') x ++;
		else if(S[i] == 'W') y --;
		else y ++;
		
		push(x, y);
		
		lx = min(lx, x); rx = max(rx, x);
		ly = min(ly, y); ry = max(ry, y);
	}
	
	compress(V);
	compress(E1);
	compress(E2);
	compress(F);
	
	v = e1 = e2 = f = 0;
	
	for(i=1; i<=r+1; i++){
		for(; v<V.size() && V[v].first == i; v++){
			T.insert(V[v].second, -1);
		}
		
		for(; e1<E1.size() && E1[e1].first == i; e1++){
			T.insert(E1[e1].second, 1);
			R1[i].push_back(E1[e1].second);
		}
		
		for(; e2<E2.size() && E2[e2].first == i; e2++){
			T.insert(E2[e2].second, 1);
			C1[E2[e2].second].push_back(i);
		}
		
		for(; f<F.size() && F[f].first == i; f++){
			T.insert(F[f].second, -1);
			R2[i].push_back(F[f].second);
			C2[F[f].second].push_back(i);
		}
		
		T.root(i);
	}
}

int colour(int sr, int sc, int er, int ec)
{
	int ret = 1 + T.query(sr, sc, er, ec);
	
	ret -= lower_bound(R1[sr].begin(), R1[sr].end(), ec + 1)
		 - lower_bound(R1[sr].begin(), R1[sr].end(), sc);
	ret -= lower_bound(C1[sc].begin(), C1[sc].end(), er + 1)
		 - lower_bound(C1[sc].begin(), C1[sc].end(), sr);
	
	ret += lower_bound(R2[sr].begin(), R2[sr].end(), ec + 1)
		 - lower_bound(R2[sr].begin(), R2[sr].end(), sc + 1);
	ret += lower_bound(C2[sc].begin(), C2[sc].end(), er + 1)
		 - lower_bound(C2[sc].begin(), C2[sc].end(), sr);
		 
	ret += (sr < lx && rx < er && sc < ly && ry < ec);
	
    return ret;
}

Compilation message (stderr)

rainbow.cpp: In member function 'void pst::insert(int, int, int, int, int)':
rainbow.cpp:25:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   else if(i <= (s + e >> 1)){
                 ~~^~~
rainbow.cpp:27:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    insert(T[p].l, s, s + e >> 1, i, v);
                      ~~^~~
rainbow.cpp:31:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    insert(T[p].r, (s + e >> 1) + 1, e, i, v);
                    ~~^~~
rainbow.cpp: In member function 'int pst::query(int, int, int, int, int)':
rainbow.cpp:49:34: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   else return query(T[p].l, s, s + e >> 1, l, r)
                                ~~^~~
rainbow.cpp:50:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     + query(T[p].r, (s + e >> 1) + 1, e, l, r);
                      ~~^~~
rainbow.cpp: In function 'void init(int, int, int, int, int, char*)':
rainbow.cpp:118:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(; v<V.size() && V[v].first == i; v++){
         ~^~~~~~~~~
rainbow.cpp:122:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(; e1<E1.size() && E1[e1].first == i; e1++){
         ~~^~~~~~~~~~
rainbow.cpp:127:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(; e2<E2.size() && E2[e2].first == i; e2++){
         ~~^~~~~~~~~~
rainbow.cpp:132:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(; f<F.size() && F[f].first == i; f++){
         ~^~~~~~~~~

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