제출 #265412

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
265412		shayan_p	무지개나라 (APIO17_rainbow)	C++14	35 / 100	3083 ms	285560 KiB

rainbow

// 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 / 11
• Subtask 2: 0 / 12
• Subtask 3: 24 / 24
• Subtask 4: 0 / 27
• Subtask 5: 0 / 26