oj.uz

Submission #1090063

# Submission time Handle Problem Language Result Execution time Memory
1090063 2024-09-17T16:36:57 Z alexander707070 Land of the Rainbow Gold (APIO17_rainbow) C++14
0 / 100
 2409 ms 827216 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 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,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--;

    if(minx>ar and maxx<br and miny>ac and maxy<bc){
        cout<<1/0;
    }

    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;
}*/

Compilation message

rainbow.cpp: In function 'int colour(int, int, int, int)':
rainbow.cpp:185:16: warning: division by zero [-Wdiv-by-zero]
  185 |         cout<<1/0;
      |               ~^~

Subtask #1
0 / 11.0

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

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 200788 KB Output is correct
2 Incorrect 229 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 226 ms 200824 KB Output is correct
2 Correct 2409 ms 422012 KB Output is correct
3 Correct 2329 ms 827216 KB Output is correct
4 Correct 2346 ms 615992 KB Output is correct
5 Correct 1836 ms 570148 KB Output is correct
6 Correct 607 ms 220760 KB Output is correct
7 Runtime error 1054 ms 479312 KB Execution killed with signal 4
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

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

Subtask #5
0 / 26.0

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