Submission #1090072

#	Time	Username	Problem	Language	Result	Execution time	Memory
1090072		alexander707070	Land of the Rainbow Gold (APIO17_rainbow)	C++14	74 / 100	3085 ms	830624 KiB

rainbow

#include<bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include "rainbow.h"

#define MAXN 200007
using namespace std;

const int maxs=2e5+7;

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

    vector<node> tree;
    int num;

    void init(){
        tree.push_back({0,0,0});
        tree.push_back({0,0,0});
        num=1;
    }

    void addnode(){
        tree.push_back({0,0,0});
        num++;
    }

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

            if(tree[v].l==0){
                addnode(); tree[v].l=num;
            }
            if(tree[v].r==0){
                addnode(); tree[v].r=num;
            }

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

            tree[v].val=tree[tree[v].l].val+tree[tree[v].r].val;
        }
    }

    int getsum(int v,int l,int r,int ll,int rr){
        if(ll>rr or v==0)return 0;

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

struct ST2D{
    struct node{
        ST t;
    };

    node tree[4*MAXN];

    void init(){
        for(int i=1;i<4*MAXN;i++){
            tree[i].t.init();
        }
    }

    void update(int v,int l,int r,int x,int y){
        if(l==r){
            tree[v].t.update(1,1,maxs,y);
        }else{
            int tt=(l+r)/2;

            if(x<=tt)update(2*v,l,tt,x,y);
            else update(2*v+1,tt+1,r,x,y);

            tree[v].t.update(1,1,maxs,y);
        }
    }

    int getsum(int v,int l,int r,int lx,int rx,int ly,int ry){
        if(lx>rx or v==0)return 0;

        if(l==lx and r==rx){
            return tree[v].t.getsum(1,1,maxs,ly,ry);
        }else{
            int tt=(l+r)/2;
            return getsum(2*v,l,tt,lx,min(tt,rx),ly,ry) + getsum(2*v+1,tt+1,r,max(tt+1,lx),rx,ly,ry);
        }
    }

}rivers,vertices,edgesh,edgesv;

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

void add(int x,int y){
    if(riv[{x,y}]==0){
        rivers.update(1,1,maxs,x,y);
        riv[{x,y}]=1;
    }

    for(int i=0;i<=1;i++){
        for(int f=0;f<=1;f++){
            if(ver[{x+i,y+f}]==1)continue;

            vertices.update(1,1,maxs,x+i,y+f);
            ver[{x+i,y+f}]=1;
        }
    }

    for(int i=0;i<=0;i++){
        for(int f=0;f<=1;f++){
            if(ev[{x+i,y+f}]==1)continue;

            edgesv.update(1,1,maxs,x+i,y+f);
            ev[{x+i,y+f}]=1;
        }
    }

    for(int i=0;i<=1;i++){
        for(int f=0;f<=0;f++){
            if(eh[{x+i,y+f}]==1)continue;

            edgesh.update(1,1,maxs,x+i,y+f);
            eh[{x+i,y+f}]=1;
        }
    }
}

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

    x=sr; y=sc;

    rivers.init();
    edgesh.init();
    edgesv.init();
    vertices.init();

    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);
    }
}

int colour(int ar,int ac,int br,int bc){
    int R=rivers.getsum(1,1,maxs,ar,br,ac,bc);
    int V=vertices.getsum(1,1,maxs,ar+1,br,ac+1,bc) + 2*(bc-ac+2) + 2*(br-ar+2) - 4;
    int E=edgesv.getsum(1,1,maxs,ar,br,ac+1,bc) + edgesh.getsum(1,1,maxs,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<<"bro";

    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: 0 / 26