Submission #155898

#	Time	Username	Problem	Language	Result	Execution time	Memory
155898		mhy908	Land of the Rainbow Gold (APIO17_rainbow)	C++14	100 / 100	1975 ms	223260 KiB

rainbow

#include "rainbow.h"
#include <bits/stdc++.h>
#define pb push_back
#define all(t) t.begin(), t.end()
using namespace std;
typedef long long LL;
struct MERGE_SORT_TREE {
    struct NODE {
        int st, fin;
        vector<int> vc;
    };
    NODE tree[1000010];
    int x;
    void initt(int point, int num){
        if(num==1){
            x++;
            tree[point].st=x;
            tree[point].fin=x;
        }
        if(num<=1)return;
        initt(point*2, num-num/2);
        initt(point*2+1, num/2);
        tree[point].st=tree[point*2].st;
        tree[point].fin=tree[point*2+1].fin;
    }
    void in_MST(int point, int num, int p) {
        tree[point].vc.pb(p);
        if(tree[point].st==tree[point].fin)return;
        int mid=(tree[point].st+tree[point].fin)/2;
        if(num<=mid)in_MST(point*2, num, p);
        else in_MST(point*2+1, num, p);
    }
    void relax(int point){
        sort(all(tree[point].vc));
        if(tree[point].st==tree[point].fin)return;
        relax(point*2);
        relax(point*2+1);
    }
    int sumrange(int point, int xl, int xr, int yl, int yr){
        int ret;
        if(tree[point].st>=xl&&tree[point].fin<=xr)
            return ret=upper_bound(all(tree[point].vc), yr)-lower_bound(all(tree[point].vc), yl);
        if(tree[point].st>xr||tree[point].fin<xl)return 0;
        return sumrange(point*2, xl, xr, yl, yr)+sumrange(point*2+1, xl, xr, yl, yr);
    }
    MERGE_SORT_TREE(){x=0; initt(1, 200010);}
    void update(LL num, LL p){
        in_MST(1, (int)num, (int)p);
    }
    int get_sum(int xl, int yl, int xr, int yr){
        if(xl>xr||yl>yr)return 0;
        return sumrange(1, xl, xr, yl, yr);
    }
};
MERGE_SORT_TREE segv, segdown, segright, segreal;
int n, m;
unordered_set<LL> s1, s2, s3, s4;
void inseg(int xx, int yy)
{
    LL x=(LL)xx, y=(LL)yy;
    if(!s1.count(300000*x+y)){
        s1.insert(300000*x+y);
        segv.update(x, y);
    }
    x++;
    if(!s1.count(300000*x+y)){
        s1.insert(300000*x+y);
        segv.update(x, y);
    }
    x--;
    y++;
    if(!s1.count(300000*x+y)){
        s1.insert(300000*x+y);
        segv.update(x, y);
    }
    x++;
    if(!s1.count(300000*x+y)){
        s1.insert(300000*x+y);
        segv.update(x, y);
    }
    x--;
    y--;
    if(!s2.count(300000*x+y)){
        s2.insert(300000*x+y);
        segdown.update(x, y);
    }
    y++;
    if(!s2.count(300000*x+y)){
        s2.insert(300000*x+y);
        segdown.update(x, y);
    }
    y--;
    if(!s3.count(300000*x+y)){
        s3.insert(300000*x+y);
        segright.update(x, y);
    }
    x++;
    if(!s3.count(300000*x+y)){
        s3.insert(300000*x+y);
        segright.update(x, y);
    }
    x--;
    if(!s4.count(300000*x+y)){
        s4.insert(300000*x+y);
        segreal.update(x, y);
    }
}
void init(int R, int C, int sr, int sc, int M, char S[]){
    n=R;
    m=C;
    inseg(sr, sc);
    for(int i=0; i<M; i++){
        if(S[i]=='N')sr--;
        if(S[i]=='S')sr++;
        if(S[i]=='W')sc--;
        if(S[i]=='E')sc++;
        inseg(sr, sc);
    }
    segreal.relax(1);
    segv.relax(1);
    segdown.relax(1);
    segright.relax(1);
}
int colour(int xst, int yst, int xfin, int yfin){
    int realv=segreal.get_sum(xst, yst, xfin, yfin);
    int v=segv.get_sum(xst+1, yst+1, xfin, yfin)+2*(xfin-xst+yfin-yst+2);
    int e=segdown.get_sum(xst, yst+1, xfin, yfin)+segright.get_sum(xst+1, yst, xfin, yfin)+2*(xfin-xst+yfin-yst+2);
    int c;
    if(!realv)c=1;
    else if(segreal.get_sum(xst, yst, xst, yfin)||segreal.get_sum(xfin, yst, xfin, yfin)||segreal.get_sum(xst, yst, xfin, yst)||segreal.get_sum(xst, yfin, xfin, yfin))c=1;
    else c=2;
    return e-v+c-realv;
}

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