oj.uz

Submission #115114

# Submission time Handle Problem Language Result Execution time Memory
115114 2019-06-05T10:47:00 Z 김세빈(#2863) Land of the Rainbow Gold (APIO17_rainbow) C++14
12 / 100
 647 ms 272848 KB 
#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[20202020];
	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;

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);
	
	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);
	}
	
	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);
	
    return ret;
}

Compilation message

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:112:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(; v<V.size() && V[v].first == i; v++){
         ~^~~~~~~~~
rainbow.cpp:116:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(; e1<E1.size() && E1[e1].first == i; e1++){
         ~~^~~~~~~~~~
rainbow.cpp:121:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(; e2<E2.size() && E2[e2].first == i; e2++){
         ~~^~~~~~~~~~
rainbow.cpp:126:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(; f<F.size() && F[f].first == i; f++){
         ~^~~~~~~~~

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 256508 KB Output is correct
2 Correct 197 ms 256760 KB Output is correct
3 Incorrect 195 ms 256632 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 192 ms 256464 KB Output is correct
2 Correct 195 ms 256540 KB Output is correct
3 Correct 457 ms 266624 KB Output is correct
4 Correct 644 ms 272728 KB Output is correct
5 Correct 647 ms 272188 KB Output is correct
6 Correct 509 ms 269120 KB Output is correct
7 Correct 560 ms 269208 KB Output is correct
8 Correct 320 ms 265256 KB Output is correct
9 Correct 581 ms 272452 KB Output is correct
10 Correct 589 ms 271812 KB Output is correct
11 Correct 536 ms 269168 KB Output is correct
12 Correct 428 ms 271684 KB Output is correct
13 Correct 451 ms 272348 KB Output is correct
14 Correct 438 ms 271916 KB Output is correct
15 Correct 410 ms 269136 KB Output is correct
16 Correct 505 ms 268144 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 256504 KB Output is correct
2 Correct 375 ms 272848 KB Output is correct
3 Correct 295 ms 272636 KB Output is correct
4 Correct 311 ms 270660 KB Output is correct
5 Correct 304 ms 269720 KB Output is correct
6 Correct 275 ms 265280 KB Output is correct
7 Incorrect 301 ms 265916 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 256508 KB Output is correct
2 Correct 197 ms 256760 KB Output is correct
3 Incorrect 195 ms 256632 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 256508 KB Output is correct
2 Correct 197 ms 256760 KB Output is correct
3 Incorrect 195 ms 256632 KB Output isn't correct
4 Halted 0 ms 0 KB -