oj.uz

Submission #1090056

# Submission time Handle Problem Language Result Execution time Memory
1090056 2024-09-17T16:29:19 Z alexander707070 Land of the Rainbow Gold (APIO17_rainbow) C++14
0 / 100
 2462 ms 827280 KB 
#include<bits/stdc++.h>
#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 and 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,br+1,ac,bc+1);
    int E=edgesv.getsum(1,1,maxs,ar,br,ac,bc+1) + edgesh.getsum(1,1,maxs,ar,br+1,ac,bc);

    int horr=2*(bc-ac+1) - edgesh.getsum(1,1,maxs,ar,ar,ac,bc) - edgesh.getsum(1,1,maxs,br+1,br+1,ac,bc) ;
    int verr=2*(br-ar+1) - edgesv.getsum(1,1,maxs,ar,br,ac,ac) - edgesv.getsum(1,1,maxs,ar,br,bc+1,bc+1) ;

    int Vhor=2*(bc-ac+2) - vertices.getsum(1,1,maxs,ar,ar,ac,bc+1) - vertices.getsum(1,1,maxs,br+1,br+1,ac,bc+1) ;
    int Vver=2*(br-ar+2) - vertices.getsum(1,1,maxs,ar,br+1,ac,ac) - vertices.getsum(1,1,maxs,ar,br+1,bc+1,bc+1) ;

    E+=horr+verr;
    V+=Vhor+Vver;

    if(ver[{ar,ac}]==0)V--;
    if(ver[{ar,bc+1}]==0)V--;
    if(ver[{br,ac+1}]==0)V--;
    if(ver[{br+1,bc+1}]==0)V--;

    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,4,6)<<":\n";


    return 0;
}*/

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 287 ms 201040 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 226 ms 200708 KB Output is correct
2 Incorrect 214 ms 200784 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 200856 KB Output is correct
2 Correct 2462 ms 422096 KB Output is correct
3 Correct 2297 ms 827280 KB Output is correct
4 Correct 2377 ms 616184 KB Output is correct
5 Correct 1829 ms 570436 KB Output is correct
6 Correct 608 ms 220756 KB Output is correct
7 Incorrect 963 ms 236628 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 287 ms 201040 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 287 ms 201040 KB Output isn't correct
2 Halted 0 ms 0 KB -