oj.uz

Submission #265413

# Submission time Handle Problem Language Result Execution time Memory
265413 2020-08-14T18:56:39 Z shayan_p Land of the Rainbow Gold (APIO17_rainbow) C++14
100 / 100
 2314 ms 504132 KB 
// And you curse yourself for things you never done

#include<bits/stdc++.h>
#include "rainbow.h"

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

const int maxn = 2e5 + 10, mod = 1e9 + 7, inf = 1e9 + 10;

struct Segment{
    vector<int> v[4 * maxn], L[4 * maxn], R[4 * maxn], tdo[maxn];
    set<pii> st;
    void restart(){
	for(int i = 0; i < maxn; i++)
	    tdo[i].clear();
	st.clear();
    }
    void add(int x, int y){
	if(st.count({x, y}))
	    return;
	st.insert({x, y});
	tdo[x].PB(y);
    }
    void build(int l = 0, int r = maxn, int id = 1){
	if(r-l == 1){
	    v[id] = tdo[l];
	    sort(v[id].begin(), v[id].end());	    
	    return;
	}
	int mid = (l+r) >> 1;
	build(l, mid, 2*id);
	build(mid, r, 2*id+1);

	int pt1 = 0, pt2 = 0;
	v[id].clear(), L[id].clear(), R[id].clear();
	while(pt1 < sz(v[2*id]) || pt2 < sz(v[2*id+1])){
	    L[id].PB(pt1), R[id].PB(pt2);
	    if(pt2 == sz(v[2*id+1]) || (pt1 != sz(v[2*id]) && v[2*id][pt1] <= v[2*id+1][pt2]))
		v[id].PB(v[2*id][pt1++]);
	    else
		v[id].PB(v[2*id+1][pt2++]);
	}
	L[id].PB(pt1), R[id].PB(pt2); // important
    }
    int ask(int f, int s, int ff, int ss, int l = 0, int r = maxn, int id = 1, int ptl = -1, int ptr = -1){
	if(id == 1){
	    ptl = lower_bound(v[1].begin(), v[1].end(), ff) - v[1].begin();
	    ptr = lower_bound(v[1].begin(), v[1].end(), ss) - v[1].begin();	    
	}
	if(ptl >= ptr || r <= f || s <= l || ss <= ff || s <= f || r <= l)
	    return 0;
	if(f <= l && r <= s)
	    return ptr - ptl;
	int mid = (l+r) >> 1;
	return ask(f, s, ff, ss, l, mid, 2*id, L[id][ptl], L[id][ptr]) + ask(f, s, ff, ss, mid, r, 2*id+1, R[id][ptl], R[id][ptr]);
    }
};
Segment s1, s2, s3, s4;

int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

int MX, mx, MY, my;

void init(int N, int M, int x, int y, int n, char *s){
    s1.restart(), s2.restart(), s3.restart(), s4.restart();
    auto ok = [&](int x, int y){
		  return x >= 0 && y >= 0 && x < N && y < M;
	      };
    auto add = [&](int x, int y){
		   s1.add(x, y);
		   if(ok(x-1, y))
		       s2.add(x-1, y);
		   if(ok(x+1, y))
		       s2.add(x, y);
		   if(ok(x, y-1))
		       s3.add(x, y-1);
		   if(ok(x, y+1))
		       s3.add(x, y);
		   
		   if(ok(x-1, y-1))
		       s4.add(x-1, y-1);
		   if(ok(x-1, y+1))
		       s4.add(x-1, y);
		   if(ok(x+1, y-1))
		       s4.add(x, y-1);
		   if(ok(x+1, y+1))
		       s4.add(x, y);
	       };    
    --x, --y;
    add(x, y);
    MX = mx = x, MY = my = y;
    for(int i = 0; i < n; i++){
	char c = s[i];
	if(c == 'N')
	    x--;
	if(c == 'W')
	    y--;
	if(c == 'S')
	    x++;
	if(c == 'E')
	    y++;
	add(x, y);
	MX = max(MX, x);
	mx = min(mx, x);
	MY = max(MY, y);
	my = min(my, y);
    }
    s1.build(), s2.build(), s3.build(), s4.build();
}

int colour(int x, int y, int xx, int yy){    
    --x, --y;    
    int A = (xx-x) * (yy-y) - s1.ask(x, xx, y, yy);
    int B = (yy-y) * (xx-x-1) - s2.ask(x, xx-1, y, yy);
    int C = (xx-x) * (yy-y-1) - s3.ask(x, xx, y, yy-1);
    int D = (xx-x-1) * (yy-y-1) - s4.ask(x, xx-1, y, yy-1);
    if(x < mx && MX < xx-1 && y < my && MY < yy-1)
	D++;
    return A + D - B - C;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 364 ms 295032 KB Output is correct
2 Correct 430 ms 296312 KB Output is correct
3 Correct 370 ms 295032 KB Output is correct
4 Correct 356 ms 295176 KB Output is correct
5 Correct 430 ms 296700 KB Output is correct
6 Correct 349 ms 294776 KB Output is correct
7 Correct 394 ms 294904 KB Output is correct
8 Correct 354 ms 294860 KB Output is correct
9 Correct 363 ms 294776 KB Output is correct
10 Correct 351 ms 294648 KB Output is correct
11 Correct 370 ms 295416 KB Output is correct
12 Correct 416 ms 295928 KB Output is correct
13 Correct 422 ms 297336 KB Output is correct
14 Correct 442 ms 297976 KB Output is correct
15 Correct 370 ms 294648 KB Output is correct
16 Correct 388 ms 294648 KB Output is correct
17 Correct 351 ms 294584 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 388 ms 294648 KB Output is correct
2 Correct 351 ms 294584 KB Output is correct
3 Correct 1234 ms 359344 KB Output is correct
4 Correct 1602 ms 399352 KB Output is correct
5 Correct 1536 ms 396608 KB Output is correct
6 Correct 1124 ms 371716 KB Output is correct
7 Correct 1549 ms 370624 KB Output is correct
8 Correct 505 ms 296056 KB Output is correct
9 Correct 1587 ms 399524 KB Output is correct
10 Correct 1632 ms 396388 KB Output is correct
11 Correct 1290 ms 371436 KB Output is correct
12 Correct 913 ms 392840 KB Output is correct
13 Correct 905 ms 399244 KB Output is correct
14 Correct 900 ms 396656 KB Output is correct
15 Correct 842 ms 371584 KB Output is correct
16 Correct 1290 ms 370044 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 370 ms 294648 KB Output is correct
2 Correct 893 ms 459824 KB Output is correct
3 Correct 1324 ms 500124 KB Output is correct
4 Correct 1235 ms 501156 KB Output is correct
5 Correct 955 ms 440552 KB Output is correct
6 Correct 623 ms 329336 KB Output is correct
7 Correct 769 ms 362080 KB Output is correct
8 Correct 818 ms 394876 KB Output is correct
9 Correct 787 ms 390688 KB Output is correct
10 Correct 560 ms 329552 KB Output is correct
11 Correct 666 ms 371648 KB Output is correct
12 Correct 872 ms 459708 KB Output is correct
13 Correct 1325 ms 500008 KB Output is correct
14 Correct 1194 ms 501180 KB Output is correct
15 Correct 1000 ms 440640 KB Output is correct
16 Correct 578 ms 323064 KB Output is correct
17 Correct 690 ms 362840 KB Output is correct
18 Correct 901 ms 470324 KB Output is correct
19 Correct 986 ms 450108 KB Output is correct
20 Correct 975 ms 450000 KB Output is correct
21 Correct 716 ms 394908 KB Output is correct
22 Correct 696 ms 390656 KB Output is correct
23 Correct 516 ms 329552 KB Output is correct
24 Correct 696 ms 371688 KB Output is correct
25 Correct 874 ms 459776 KB Output is correct
26 Correct 1360 ms 500120 KB Output is correct
27 Correct 1333 ms 501192 KB Output is correct
28 Correct 968 ms 440536 KB Output is correct
29 Correct 552 ms 322936 KB Output is correct
30 Correct 677 ms 362952 KB Output is correct
31 Correct 905 ms 470256 KB Output is correct
32 Correct 1034 ms 450140 KB Output is correct
33 Correct 987 ms 450160 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 364 ms 295032 KB Output is correct
2 Correct 430 ms 296312 KB Output is correct
3 Correct 370 ms 295032 KB Output is correct
4 Correct 356 ms 295176 KB Output is correct
5 Correct 430 ms 296700 KB Output is correct
6 Correct 349 ms 294776 KB Output is correct
7 Correct 394 ms 294904 KB Output is correct
8 Correct 354 ms 294860 KB Output is correct
9 Correct 363 ms 294776 KB Output is correct
10 Correct 351 ms 294648 KB Output is correct
11 Correct 370 ms 295416 KB Output is correct
12 Correct 416 ms 295928 KB Output is correct
13 Correct 422 ms 297336 KB Output is correct
14 Correct 442 ms 297976 KB Output is correct
15 Correct 370 ms 294648 KB Output is correct
16 Correct 388 ms 294648 KB Output is correct
17 Correct 351 ms 294584 KB Output is correct
18 Correct 2051 ms 393144 KB Output is correct
19 Correct 780 ms 302840 KB Output is correct
20 Correct 642 ms 299000 KB Output is correct
21 Correct 692 ms 299768 KB Output is correct
22 Correct 739 ms 300792 KB Output is correct
23 Correct 902 ms 302712 KB Output is correct
24 Correct 739 ms 299704 KB Output is correct
25 Correct 759 ms 300536 KB Output is correct
26 Correct 758 ms 301304 KB Output is correct
27 Correct 1159 ms 371000 KB Output is correct
28 Correct 1099 ms 333868 KB Output is correct
29 Correct 1394 ms 364396 KB Output is correct
30 Correct 2033 ms 473216 KB Output is correct
31 Correct 361 ms 294904 KB Output is correct
32 Correct 2217 ms 372228 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 364 ms 295032 KB Output is correct
2 Correct 430 ms 296312 KB Output is correct
3 Correct 370 ms 295032 KB Output is correct
4 Correct 356 ms 295176 KB Output is correct
5 Correct 430 ms 296700 KB Output is correct
6 Correct 349 ms 294776 KB Output is correct
7 Correct 394 ms 294904 KB Output is correct
8 Correct 354 ms 294860 KB Output is correct
9 Correct 363 ms 294776 KB Output is correct
10 Correct 351 ms 294648 KB Output is correct
11 Correct 370 ms 295416 KB Output is correct
12 Correct 416 ms 295928 KB Output is correct
13 Correct 422 ms 297336 KB Output is correct
14 Correct 442 ms 297976 KB Output is correct
15 Correct 370 ms 294648 KB Output is correct
16 Correct 388 ms 294648 KB Output is correct
17 Correct 351 ms 294584 KB Output is correct
18 Correct 2051 ms 393144 KB Output is correct
19 Correct 780 ms 302840 KB Output is correct
20 Correct 642 ms 299000 KB Output is correct
21 Correct 692 ms 299768 KB Output is correct
22 Correct 739 ms 300792 KB Output is correct
23 Correct 902 ms 302712 KB Output is correct
24 Correct 739 ms 299704 KB Output is correct
25 Correct 759 ms 300536 KB Output is correct
26 Correct 758 ms 301304 KB Output is correct
27 Correct 1159 ms 371000 KB Output is correct
28 Correct 1099 ms 333868 KB Output is correct
29 Correct 1394 ms 364396 KB Output is correct
30 Correct 2033 ms 473216 KB Output is correct
31 Correct 361 ms 294904 KB Output is correct
32 Correct 2217 ms 372228 KB Output is correct
33 Correct 893 ms 459824 KB Output is correct
34 Correct 1324 ms 500124 KB Output is correct
35 Correct 1235 ms 501156 KB Output is correct
36 Correct 955 ms 440552 KB Output is correct
37 Correct 623 ms 329336 KB Output is correct
38 Correct 769 ms 362080 KB Output is correct
39 Correct 818 ms 394876 KB Output is correct
40 Correct 787 ms 390688 KB Output is correct
41 Correct 560 ms 329552 KB Output is correct
42 Correct 666 ms 371648 KB Output is correct
43 Correct 872 ms 459708 KB Output is correct
44 Correct 1325 ms 500008 KB Output is correct
45 Correct 1194 ms 501180 KB Output is correct
46 Correct 1000 ms 440640 KB Output is correct
47 Correct 578 ms 323064 KB Output is correct
48 Correct 690 ms 362840 KB Output is correct
49 Correct 901 ms 470324 KB Output is correct
50 Correct 986 ms 450108 KB Output is correct
51 Correct 975 ms 450000 KB Output is correct
52 Correct 716 ms 394908 KB Output is correct
53 Correct 696 ms 390656 KB Output is correct
54 Correct 516 ms 329552 KB Output is correct
55 Correct 696 ms 371688 KB Output is correct
56 Correct 874 ms 459776 KB Output is correct
57 Correct 1360 ms 500120 KB Output is correct
58 Correct 1333 ms 501192 KB Output is correct
59 Correct 968 ms 440536 KB Output is correct
60 Correct 552 ms 322936 KB Output is correct
61 Correct 677 ms 362952 KB Output is correct
62 Correct 905 ms 470256 KB Output is correct
63 Correct 1034 ms 450140 KB Output is correct
64 Correct 987 ms 450160 KB Output is correct
65 Correct 2115 ms 398236 KB Output is correct
66 Correct 2314 ms 393960 KB Output is correct
67 Correct 1745 ms 332948 KB Output is correct
68 Correct 1636 ms 374628 KB Output is correct
69 Correct 1135 ms 462572 KB Output is correct
70 Correct 1623 ms 503572 KB Output is correct
71 Correct 1328 ms 504132 KB Output is correct
72 Correct 1151 ms 442956 KB Output is correct
73 Correct 670 ms 326756 KB Output is correct
74 Correct 804 ms 366476 KB Output is correct
75 Correct 1104 ms 473128 KB Output is correct
76 Correct 1184 ms 452392 KB Output is correct
77 Correct 1312 ms 452540 KB Output is correct
78 Correct 1234 ms 359344 KB Output is correct
79 Correct 1602 ms 399352 KB Output is correct
80 Correct 1536 ms 396608 KB Output is correct
81 Correct 1124 ms 371716 KB Output is correct
82 Correct 1549 ms 370624 KB Output is correct
83 Correct 505 ms 296056 KB Output is correct
84 Correct 1587 ms 399524 KB Output is correct
85 Correct 1632 ms 396388 KB Output is correct
86 Correct 1290 ms 371436 KB Output is correct
87 Correct 913 ms 392840 KB Output is correct
88 Correct 905 ms 399244 KB Output is correct
89 Correct 900 ms 396656 KB Output is correct
90 Correct 842 ms 371584 KB Output is correct
91 Correct 1290 ms 370044 KB Output is correct