Submission #1132623

#	Time	Username	Problem	Language	Result	Execution time	Memory
1132623		shjeong	Land of the Rainbow Gold (APIO17_rainbow)	C++20	12 / 100	524 ms	435888 KiB

rainbow

#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pi;
#define all(x) x.begin(),x.end()
#define COMP(x) x.erase(unique(all(x)),x.end())
#define sz(x) x.size()
vector<pi> white_grid; //흰색(강) 그리드 위치 관리
vector<int> white[202020];
ll n, m;
struct PST{
    struct Node{
        int l,r,v;
        Node(): l(-1), r(-1), v(0){}
    };
    int M=0;
    vector<Node> tree; vector<int> root;
    //트리 1개에 O(C), 업데이트가 O(M)개 있다고 생각하면 O(C+ClogM) 대충 200000*21*4 900만개 정도. 2~4배 정도 뛸수 있음
    void init(int node, int s, int e){
        if(s==e)return;
        ll mid = s+e>>1;
        tree[node].l = ++M;
        tree[node].r = ++M;
        init(tree[node].l,s,mid); init(tree[node].r,mid+1,e);
    }
    void upd_tree(int cur, int prv, int s, int e, int i, int d){  //i에 d를 더하기
        if(s==e){
            tree[cur].v = (prv<0?0:tree[prv].v)+d;
            return;
        }
        int mid = s+e>>1;
        if(i<=mid){
            //L은 새로 만들고 R은 그대로
            tree[cur].l = ++M;
            tree[cur].r = tree[prv].r;
            upd_tree(tree[cur].l,tree[prv].l,s,mid,i,d);
        }
        else{
            tree[cur].r = ++M;
            tree[cur].l = tree[prv].l;
            upd_tree(tree[cur].r,tree[prv].r,mid+1,e,i,d);
        }
        tree[cur].v = (tree[cur].l>=0?tree[tree[cur].l].v:0) + (tree[cur].r>=0?tree[tree[cur].r].v:0);
    }
    int query(int node, int s, int e, int l, int r){
        if(node<0 or e<l or r<s)return 0;
        if(l<=s and e<=r)return tree[node].v;
        ll mid = s+e>>1; return query(tree[node].l,s,mid,l,r) + query(tree[node].r,mid+1,e,l,r);
    }
    int sum(int x1, int y1, int x2, int y2){
        return query(root[x2],1,m,y1,y2) - query(root[x1-1],1,m,y1,y2);
    }
    ll single_sum(int x1, int y1){ if(x1<=0 or y1<=0)return 0; return (ll)x1*y1 - query(root[x1],1,m,1,y1); }
    ll single_sum2(int x1, int y1){ if(x1<=0 or y1<=0)return 0; return (ll)(x1-1)*(y1-1) - query(root[x1],1,m,1,y1); }  //Black
    ll single_sum3(int x1, int y1){ if(x1<=0 or y1<=0)return 0; return (ll)x1*y1 - query(root[x1],1,m,1,y1); }  //Down
    ll single_sum4(int x1, int y1){ if(x1<=0 or y1<=0)return 0; return (ll)x1*y1 - query(root[x1],1,m,1,y1); }  //Right
    int rev_single_sum(int x1, int y1){ if(x1<=0 or y1<=0)return 0; return query(root[x1],1,m,1,y1); }
}W,B,R,D;
void init(int RR, int CC, int r, int c, int M, char *S) {
    n=RR,m=CC;
    white_grid.push_back({r,c});
    for(int i = 0 ; i < M ; i++){
        if(S[i]=='N')r--;
        if(S[i]=='S')r++;
        if(S[i]=='E')c++;
        if(S[i]=='W')c--;
        white_grid.push_back({r,c});
    }
    sort(all(white_grid)); COMP(white_grid);
    for(auto [i,j] : white_grid)white[i].push_back(j);
    W.tree.resize(9000000); W.root.resize(n+1); W.init(0,1,m);
    B.tree.resize(9000000); B.root.resize(n+1); B.init(0,1,m);
    R.tree.resize(9000000); R.root.resize(n+1); R.init(0,1,m);
    D.tree.resize(9000000); D.root.resize(n+1); D.init(0,1,m);
    //White : (i,j)가 white일 때 1
    ll prv_root = 0;
    for(int i = 1 ; i <= n ; i++){
        ll prv_root = W.root[i-1];
        for(auto j : white[i]){
            ll cur = ++W.M;
            W.upd_tree(cur,prv_root,1,m,j,1);
            prv_root = cur;
        }
        W.root[i] = prv_root;
    }
    //Black : (i,j), (i,j-1), (i-1,j), (i-1,j-1)중 하나라도 white일 때 1
    for(int i = 1 ; i <= n ; i++)white[i].clear();
    for(auto [i,j] : white_grid){
        vector<pi> v = {{0,0},{0,1},{1,0},{1,1}};
        for(auto [di,dj] : v){
            int ni = i+di, nj = j+dj;
            if(ni<1 or nj<1 or ni>n or nj>m)continue;
            white[ni].push_back(nj);
        }
    }
    prv_root = 0;
    for(int i = 1 ; i <= n ; i++){
        ll prv_root = B.root[i-1];
        sort(all(white[i])); COMP(white[i]);
        for(auto j : white[i]){
            ll cur = ++B.M;
            B.upd_tree(cur,prv_root,1,m,j,1);
            prv_root = cur;
        }
        B.root[i] = prv_root;
    }
    //Right : (i,j)와 (i,j+1) 중 하나라도 white일 때 1
    for(int i = 1 ; i <= n ; i++)white[i].clear();
    for(auto [i,j] : white_grid){
        for(int k = -1 ; k <= 0 ; k++){
            int ni = i, nj = j+k;
            if(nj<1 or nj>m)continue;
            white[ni].push_back(nj);
        }
    }
    prv_root = 0;
    for(int i = 1 ; i <= n ; i++){
        ll prv_root = R.root[i-1];
        sort(all(white[i])); COMP(white[i]);
        for(auto j : white[i]){
            ll cur = ++R.M;
            R.upd_tree(cur,prv_root,1,m,j,1);
            prv_root = cur;
        }
        R.root[i] = prv_root;
    }
    //Down : (i,j)와 (i+1,j)
    for(int i = 1 ; i <= n ; i++)white[i].clear();
    for(auto [i,j] : white_grid){
        for(int k = -1 ; k <= 0 ; k++){
            int ni = i+k, nj = j;
            if(ni<1 or ni>n)continue;
            white[ni].push_back(nj);
        }
    }
    prv_root = 0;
    for(int i = 1 ; i <= n ; i++){
        ll prv_root = D.root[i-1];
        sort(all(white[i])); COMP(white[i]);
        for(auto j : white[i]){
            ll cur = ++D.M;
            D.upd_tree(cur,prv_root,1,m,j,1);
            prv_root = cur;
        }
        D.root[i] = prv_root;
    }
}

int colour(int x1, int y1, int x2, int y2) {
    ll N = x2-x1+1, M = y2-y1+1;
    ll v = (N+1)*(M+1) - (B.single_sum2(x2,y2) - B.single_sum2(x2,y1) - B.single_sum2(x1,y2) + B.single_sum2(x1,y1));
    ll e = N*(M+1)+M*(N+1) - (D.single_sum3(x2-1,y2) - D.single_sum3(x2-1,y1-1) - D.single_sum3(x1-1,y2) + D.single_sum3(x1-1,y1-1)) - (R.single_sum4(x2,y2-1) - R.single_sum4(x2,y1-1) - R.single_sum4(x1-1,y2-1) + R.single_sum4(x1-1,y1-1));
    ll w = W.rev_single_sum(x2,y2) - W.rev_single_sum(x2,y1-1) - W.rev_single_sum(x1-1,y2) + W.rev_single_sum(x1-1,y1-1);
    //cout<<v<<" "<<e<<" "<<w<<endl;
    return 1-v+e-w;
}

• Subtask 1: 0 / 11
• Subtask 2: 12 / 12
• Subtask 3: 0 / 24
• Subtask 4: 0 / 27
• Subtask 5: 0 / 26