Submission #1090290

#	Time	Username	Problem	Language	Result	Execution time	Memory
1090290		alexander707070	Land of the Rainbow Gold (APIO17_rainbow)	C++14	100 / 100	590 ms	168024 KiB

rainbow

#include<bits/stdc++.h>
#include "rainbow.h"

#define MAXN 200007
using namespace std;

const int maxs=2e5+7;

struct PST{
    struct node{
        int l,r;
        int val;
    };

    int root[MAXN],last,num=1;
    node tree[20*MAXN];
    
    void upgrade(){
        last++; root[last]=num;
    }

    int update(int v,int l,int r,int pos){
        if(l==r){
            num++;
            tree[num].val=tree[v].val+1;
            return num;
        }else{
            int tt=(l+r)/2;

            int lt,rt;
            if(pos<=tt){
                lt=update(tree[v].l,l,tt,pos);
                rt=tree[v].r;
            }else{
                lt=tree[v].l;
                rt=update(tree[v].r,tt+1,r,pos);
            }

            num++;
            tree[num].val=tree[lt].val+tree[rt].val;
            tree[num].l=lt; tree[num].r=rt;

            return num;
        }
    }

    int getsum(int v1,int v2,int l,int r,int ll,int rr){
        if(ll>rr)return 0;
        if(l==ll and r==rr){
            return tree[v2].val-tree[v1].val;
        }else{
            int tt=(l+r)/2;
            return getsum(tree[v1].l,tree[v2].l,l,tt,ll,min(tt,rr)) + getsum(tree[v1].r,tree[v2].r,tt+1,r,max(tt+1,ll),rr);
        }
    }

    void build(set< pair<int,int> > &s){
        auto it=s.begin();

        for(int i=1;i<=maxs;i++){
            while(it!=s.end()){
                pair<int,int> curr=*it;
                if(curr.first==i)update(num,1,maxs,curr.second);
                else break;

                it++;
            }

            upgrade();
        }
    }

    int query(int a,int c,int b,int d){
        return getsum(root[a-1],root[c],1,maxs,b,d);
    }
}rivers,vertices,edgesh,edgesv;

int n,m,x,y,minx,miny,maxx,maxy;
set< pair<int,int> > ver,eh,ev,riv;

void add(int x,int y){
    ver.insert({x,y});
    ver.insert({x+1,y});
    ver.insert({x,y+1});
    ver.insert({x+1,y+1});

    riv.insert({x,y});

    ev.insert({x,y});
    ev.insert({x,y+1});

    eh.insert({x,y});
    eh.insert({x+1,y});
}

void init(int R, int C, int sr, int sc, int M, char *S) {
    n=R; m=C;

    x=sr; y=sc;

    add(x,y);
    minx=maxx=x;
    miny=maxy=y;

    for(int i=0;i<M;i++){
        if(S[i]=='N')x--;
        if(S[i]=='S')x++;
        if(S[i]=='E')y++;
        if(S[i]=='W')y--;
        add(x,y);

        minx=min(minx,x);
        miny=min(miny,y);

        maxx=max(maxx,x);
        maxy=max(maxy,y);
    }

    rivers.build(riv);
    edgesh.build(eh);
    edgesv.build(ev);
    vertices.build(ver);
}

int colour(int ar,int ac,int br,int bc){
    int R=rivers.query(ar,br,ac,bc);
    int V=vertices.query(ar+1,br,ac+1,bc) + 2*(bc-ac+2) + 2*(br-ar+2) - 4;
    int E=edgesv.query(ar,br,ac+1,bc) + edgesh.query(ar+1,br,ac,bc) + 2*(bc-ac+1) + 2*(br-ar+1) ;

    if(minx>ar and maxx<br and miny>ac and maxy<bc)E++;

    return E-V-R+1;
}

/*int main(){
   
    init(6, 4,3, 3, 9,"NWESSWEWS");

    cout<<colour(2,3, 2, 3)<<"\n";
    cout<<colour(3,2,4,4)<<"\n";
    cout<<colour(5,3,6,4)<<"\n";
    cout<<colour(1,2,5,3)<<"\n";
    cout<<colour(1,1,6,4)<<":\n";


    return 0;
}*/

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