oj.uz

Submission #265412

# Submission time Handle Problem Language Result Execution time Memory
265412 2020-08-14T18:55:59 Z shayan_p Land of the Rainbow Gold (APIO17_rainbow) C++14
35 / 100
 3000 ms 285560 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]);

	*/

	int ans = 0;
	for(pii p : st)
	    ans+= f <= p.F && p.F < s && ff <= p.S && p.S < ss;
	return ans;
    }
};
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 169 ms 244600 KB Output is correct
2 Correct 213 ms 244816 KB Output is correct
3 Correct 171 ms 244600 KB Output is correct
4 Correct 193 ms 244728 KB Output is correct
5 Correct 242 ms 244856 KB Output is correct
6 Correct 166 ms 244600 KB Output is correct
7 Correct 158 ms 244600 KB Output is correct
8 Correct 160 ms 244600 KB Output is correct
9 Correct 161 ms 244600 KB Output is correct
10 Correct 158 ms 244600 KB Output is correct
11 Correct 177 ms 244728 KB Output is correct
12 Correct 206 ms 244856 KB Output is correct
13 Correct 263 ms 245112 KB Output is correct
14 Correct 262 ms 245112 KB Output is correct
15 Correct 158 ms 244600 KB Output is correct
16 Correct 156 ms 244600 KB Output is correct
17 Correct 157 ms 244600 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 244600 KB Output is correct
2 Correct 157 ms 244600 KB Output is correct
3 Execution timed out 3083 ms 257136 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 244600 KB Output is correct
2 Correct 472 ms 275276 KB Output is correct
3 Correct 490 ms 285452 KB Output is correct
4 Correct 496 ms 279288 KB Output is correct
5 Correct 418 ms 272760 KB Output is correct
6 Correct 277 ms 250616 KB Output is correct
7 Correct 362 ms 256632 KB Output is correct
8 Correct 329 ms 263916 KB Output is correct
9 Correct 363 ms 263156 KB Output is correct
10 Correct 249 ms 250620 KB Output is correct
11 Correct 363 ms 258272 KB Output is correct
12 Correct 479 ms 275276 KB Output is correct
13 Correct 513 ms 285560 KB Output is correct
14 Correct 498 ms 279292 KB Output is correct
15 Correct 423 ms 272760 KB Output is correct
16 Correct 274 ms 249464 KB Output is correct
17 Correct 348 ms 256764 KB Output is correct
18 Correct 469 ms 275960 KB Output is correct
19 Correct 433 ms 275728 KB Output is correct
20 Correct 443 ms 275680 KB Output is correct
21 Correct 365 ms 263916 KB Output is correct
22 Correct 394 ms 263032 KB Output is correct
23 Correct 283 ms 250616 KB Output is correct
24 Correct 335 ms 258424 KB Output is correct
25 Correct 484 ms 275260 KB Output is correct
26 Correct 507 ms 285552 KB Output is correct
27 Correct 498 ms 279328 KB Output is correct
28 Correct 420 ms 272760 KB Output is correct
29 Correct 279 ms 249464 KB Output is correct
30 Correct 350 ms 256888 KB Output is correct
31 Correct 504 ms 276088 KB Output is correct
32 Correct 443 ms 275680 KB Output is correct
33 Correct 450 ms 275680 KB Output is correct

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 244600 KB Output is correct
2 Correct 213 ms 244816 KB Output is correct
3 Correct 171 ms 244600 KB Output is correct
4 Correct 193 ms 244728 KB Output is correct
5 Correct 242 ms 244856 KB Output is correct
6 Correct 166 ms 244600 KB Output is correct
7 Correct 158 ms 244600 KB Output is correct
8 Correct 160 ms 244600 KB Output is correct
9 Correct 161 ms 244600 KB Output is correct
10 Correct 158 ms 244600 KB Output is correct
11 Correct 177 ms 244728 KB Output is correct
12 Correct 206 ms 244856 KB Output is correct
13 Correct 263 ms 245112 KB Output is correct
14 Correct 262 ms 245112 KB Output is correct
15 Correct 158 ms 244600 KB Output is correct
16 Correct 156 ms 244600 KB Output is correct
17 Correct 157 ms 244600 KB Output is correct
18 Execution timed out 3057 ms 260632 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 244600 KB Output is correct
2 Correct 213 ms 244816 KB Output is correct
3 Correct 171 ms 244600 KB Output is correct
4 Correct 193 ms 244728 KB Output is correct
5 Correct 242 ms 244856 KB Output is correct
6 Correct 166 ms 244600 KB Output is correct
7 Correct 158 ms 244600 KB Output is correct
8 Correct 160 ms 244600 KB Output is correct
9 Correct 161 ms 244600 KB Output is correct
10 Correct 158 ms 244600 KB Output is correct
11 Correct 177 ms 244728 KB Output is correct
12 Correct 206 ms 244856 KB Output is correct
13 Correct 263 ms 245112 KB Output is correct
14 Correct 262 ms 245112 KB Output is correct
15 Correct 158 ms 244600 KB Output is correct
16 Correct 156 ms 244600 KB Output is correct
17 Correct 157 ms 244600 KB Output is correct
18 Execution timed out 3057 ms 260632 KB Time limit exceeded
19 Halted 0 ms 0 KB -