oj.uz

Submission #115113

# Submission time Handle Problem Language Result Execution time Memory
115113 2019-06-05T10:42:24 Z 김세빈(#2863) Land of the Rainbow Gold (APIO17_rainbow) C++14
12 / 100
 730 ms 275372 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[E1[e1].first].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(E2[e2].first);
		}
		
		for(; f<F.size() && F[f].first == i; f++){
			T.insert(F[f].second, -1);
			R2[F[f].first].push_back(F[f].second);
			C2[F[f].second].push_back(F[f].first);
		}
		
		T.root(i);
	}
}

int colour(int sr, int sc, int er, int ec)
{
	int ret = 1 + T.query(sr, sc, er, ec);
	
	ret -= upper_bound(R1[sr].begin(), R1[sr].end(), ec)
		 - lower_bound(R1[sr].begin(), R1[sr].end(), sc);
	ret -= upper_bound(C1[sc].begin(), C1[sc].end(), er)
		 - lower_bound(C1[sc].begin(), C1[sc].end(), sr);
	
	ret += upper_bound(R2[sr].begin(), R2[sr].end(), ec)
		 - lower_bound(R2[sr].begin(), R2[sr].end(), sc + 1);
	ret += upper_bound(C2[sc].begin(), C2[sc].end(), er)
		 - 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 256632 KB Output is correct
2 Correct 197 ms 256760 KB Output is correct
3 Incorrect 197 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 201 ms 256540 KB Output is correct
2 Correct 195 ms 256504 KB Output is correct
3 Correct 457 ms 269268 KB Output is correct
4 Correct 603 ms 275372 KB Output is correct
5 Correct 730 ms 274932 KB Output is correct
6 Correct 552 ms 272020 KB Output is correct
7 Correct 573 ms 272068 KB Output is correct
8 Correct 313 ms 268236 KB Output is correct
9 Correct 592 ms 275336 KB Output is correct
10 Correct 592 ms 274804 KB Output is correct
11 Correct 528 ms 271936 KB Output is correct
12 Correct 442 ms 274500 KB Output is correct
13 Correct 441 ms 275268 KB Output is correct
14 Correct 471 ms 274884 KB Output is correct
15 Correct 438 ms 271940 KB Output is correct
16 Correct 500 ms 270916 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 256504 KB Output is correct
2 Correct 400 ms 272960 KB Output is correct
3 Correct 298 ms 272536 KB Output is correct
4 Correct 315 ms 270968 KB Output is correct
5 Correct 292 ms 269688 KB Output is correct
6 Correct 277 ms 265432 KB Output is correct
7 Incorrect 306 ms 266044 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 256632 KB Output is correct
2 Correct 197 ms 256760 KB Output is correct
3 Incorrect 197 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 256632 KB Output is correct
2 Correct 197 ms 256760 KB Output is correct
3 Incorrect 197 ms 256632 KB Output isn't correct
4 Halted 0 ms 0 KB -