oj.uz

Submission #265411

# Submission time Handle Problem Language Result Execution time Memory
265411 2020-08-14T18:43:11 Z shayan_p Land of the Rainbow Gold (APIO17_rainbow) C++14
12 / 100
 1625 ms 501364 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;

    if(x < mx && MX < xx-1 && y < my && MY < yy-1)
	return 1;
    
    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);
    return A + D - B - C;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 340 ms 295032 KB Output is correct
2 Correct 407 ms 296312 KB Output is correct
3 Incorrect 353 ms 295160 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 344 ms 294904 KB Output is correct
2 Correct 337 ms 294648 KB Output is correct
3 Correct 1250 ms 361768 KB Output is correct
4 Correct 1625 ms 401652 KB Output is correct
5 Correct 1526 ms 399300 KB Output is correct
6 Correct 1095 ms 374128 KB Output is correct
7 Correct 1433 ms 373008 KB Output is correct
8 Correct 516 ms 298488 KB Output is correct
9 Correct 1583 ms 401768 KB Output is correct
10 Correct 1576 ms 399300 KB Output is correct
11 Correct 1328 ms 373996 KB Output is correct
12 Correct 858 ms 395200 KB Output is correct
13 Correct 857 ms 401464 KB Output is correct
14 Correct 859 ms 399176 KB Output is correct
15 Correct 830 ms 373872 KB Output is correct
16 Correct 1347 ms 372512 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 365 ms 294648 KB Output is correct
2 Correct 908 ms 459752 KB Output is correct
3 Correct 1334 ms 499984 KB Output is correct
4 Correct 1171 ms 501364 KB Output is correct
5 Correct 968 ms 440536 KB Output is correct
6 Correct 589 ms 329340 KB Output is correct
7 Incorrect 697 ms 362428 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 340 ms 295032 KB Output is correct
2 Correct 407 ms 296312 KB Output is correct
3 Incorrect 353 ms 295160 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 340 ms 295032 KB Output is correct
2 Correct 407 ms 296312 KB Output is correct
3 Incorrect 353 ms 295160 KB Output isn't correct
4 Halted 0 ms 0 KB -