oj.uz

Submission #115120

# Submission time Handle Problem Language Result Execution time Memory
115120 2019-06-05T10:56:45 Z sebinkim Land of the Rainbow Gold (APIO17_rainbow) C++14
38 / 100
 514 ms 307496 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[10101010];
	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

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 137976 KB Output is correct
2 Correct 108 ms 138104 KB Output is correct
3 Correct 105 ms 137976 KB Output is correct
4 Correct 106 ms 137976 KB Output is correct
5 Correct 115 ms 138320 KB Output is correct
6 Correct 106 ms 138072 KB Output is correct
7 Correct 104 ms 137848 KB Output is correct
8 Correct 107 ms 137976 KB Output is correct
9 Correct 104 ms 137976 KB Output is correct
10 Correct 104 ms 137976 KB Output is correct
11 Correct 106 ms 137976 KB Output is correct
12 Correct 112 ms 138232 KB Output is correct
13 Correct 110 ms 138076 KB Output is correct
14 Correct 114 ms 138412 KB Output is correct
15 Correct 109 ms 137832 KB Output is correct
16 Correct 108 ms 137920 KB Output is correct
17 Correct 111 ms 137976 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 137920 KB Output is correct
2 Correct 111 ms 137976 KB Output is correct
3 Correct 373 ms 147920 KB Output is correct
4 Incorrect 417 ms 154564 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 137832 KB Output is correct
2 Runtime error 514 ms 307496 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 137976 KB Output is correct
2 Correct 108 ms 138104 KB Output is correct
3 Correct 105 ms 137976 KB Output is correct
4 Correct 106 ms 137976 KB Output is correct
5 Correct 115 ms 138320 KB Output is correct
6 Correct 106 ms 138072 KB Output is correct
7 Correct 104 ms 137848 KB Output is correct
8 Correct 107 ms 137976 KB Output is correct
9 Correct 104 ms 137976 KB Output is correct
10 Correct 104 ms 137976 KB Output is correct
11 Correct 106 ms 137976 KB Output is correct
12 Correct 112 ms 138232 KB Output is correct
13 Correct 110 ms 138076 KB Output is correct
14 Correct 114 ms 138412 KB Output is correct
15 Correct 109 ms 137832 KB Output is correct
16 Correct 108 ms 137920 KB Output is correct
17 Correct 111 ms 137976 KB Output is correct
18 Correct 381 ms 147576 KB Output is correct
19 Correct 211 ms 139012 KB Output is correct
20 Correct 190 ms 138744 KB Output is correct
21 Correct 193 ms 138744 KB Output is correct
22 Correct 202 ms 138872 KB Output is correct
23 Correct 209 ms 139040 KB Output is correct
24 Correct 207 ms 139028 KB Output is correct
25 Correct 211 ms 139128 KB Output is correct
26 Correct 214 ms 139096 KB Output is correct
27 Correct 309 ms 147428 KB Output is correct
28 Correct 277 ms 146524 KB Output is correct
29 Correct 293 ms 147144 KB Output is correct
30 Correct 404 ms 149444 KB Output is correct
31 Correct 106 ms 137948 KB Output is correct
32 Correct 378 ms 147644 KB Output is correct

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 137976 KB Output is correct
2 Correct 108 ms 138104 KB Output is correct
3 Correct 105 ms 137976 KB Output is correct
4 Correct 106 ms 137976 KB Output is correct
5 Correct 115 ms 138320 KB Output is correct
6 Correct 106 ms 138072 KB Output is correct
7 Correct 104 ms 137848 KB Output is correct
8 Correct 107 ms 137976 KB Output is correct
9 Correct 104 ms 137976 KB Output is correct
10 Correct 104 ms 137976 KB Output is correct
11 Correct 106 ms 137976 KB Output is correct
12 Correct 112 ms 138232 KB Output is correct
13 Correct 110 ms 138076 KB Output is correct
14 Correct 114 ms 138412 KB Output is correct
15 Correct 109 ms 137832 KB Output is correct
16 Correct 108 ms 137920 KB Output is correct
17 Correct 111 ms 137976 KB Output is correct
18 Correct 381 ms 147576 KB Output is correct
19 Correct 211 ms 139012 KB Output is correct
20 Correct 190 ms 138744 KB Output is correct
21 Correct 193 ms 138744 KB Output is correct
22 Correct 202 ms 138872 KB Output is correct
23 Correct 209 ms 139040 KB Output is correct
24 Correct 207 ms 139028 KB Output is correct
25 Correct 211 ms 139128 KB Output is correct
26 Correct 214 ms 139096 KB Output is correct
27 Correct 309 ms 147428 KB Output is correct
28 Correct 277 ms 146524 KB Output is correct
29 Correct 293 ms 147144 KB Output is correct
30 Correct 404 ms 149444 KB Output is correct
31 Correct 106 ms 137948 KB Output is correct
32 Correct 378 ms 147644 KB Output is correct
33 Runtime error 514 ms 307496 KB Execution killed with signal 11 (could be triggered by violating memory limits)
34 Halted 0 ms 0 KB -