oj.uz

Submission #1090067

# Submission time Handle Problem Language Result Execution time Memory
1090067 2024-09-17T16:42:04 Z alexander707070 Land of the Rainbow Gold (APIO17_rainbow) C++14
35 / 100
 3000 ms 827296 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+1,ac}]==0)V--;
    if(ver[{br+1,bc+1}]==0)V--;

    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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 201044 KB Output is correct
2 Correct 274 ms 201832 KB Output is correct
3 Correct 286 ms 201512 KB Output is correct
4 Correct 279 ms 201452 KB Output is correct
5 Correct 276 ms 202192 KB Output is correct
6 Correct 220 ms 200792 KB Output is correct
7 Correct 227 ms 200784 KB Output is correct
8 Correct 239 ms 200840 KB Output is correct
9 Correct 232 ms 200900 KB Output is correct
10 Correct 243 ms 200784 KB Output is correct
11 Correct 238 ms 201220 KB Output is correct
12 Correct 268 ms 201804 KB Output is correct
13 Correct 276 ms 202572 KB Output is correct
14 Correct 291 ms 202576 KB Output is correct
15 Correct 227 ms 200724 KB Output is correct
16 Correct 236 ms 200728 KB Output is correct
17 Correct 232 ms 200784 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 200728 KB Output is correct
2 Correct 232 ms 200784 KB Output is correct
3 Correct 1967 ms 351436 KB Output is correct
4 Execution timed out 3009 ms 441304 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 227 ms 200724 KB Output is correct
2 Correct 2381 ms 422080 KB Output is correct
3 Correct 2359 ms 827296 KB Output is correct
4 Correct 2292 ms 616116 KB Output is correct
5 Correct 1839 ms 570148 KB Output is correct
6 Correct 608 ms 220576 KB Output is correct
7 Correct 985 ms 236472 KB Output is correct
8 Correct 2158 ms 332272 KB Output is correct
9 Correct 1893 ms 312404 KB Output is correct
10 Correct 673 ms 219824 KB Output is correct
11 Correct 1302 ms 310064 KB Output is correct
12 Correct 2390 ms 422084 KB Output is correct
13 Correct 2252 ms 827216 KB Output is correct
14 Correct 2216 ms 616132 KB Output is correct
15 Correct 1911 ms 570208 KB Output is correct
16 Correct 555 ms 216512 KB Output is correct
17 Correct 966 ms 237140 KB Output is correct
18 Correct 2044 ms 280660 KB Output is correct
19 Correct 2428 ms 625264 KB Output is correct
20 Correct 2439 ms 625136 KB Output is correct
21 Correct 2133 ms 332280 KB Output is correct
22 Correct 1898 ms 312372 KB Output is correct
23 Correct 629 ms 219728 KB Output is correct
24 Correct 1365 ms 310084 KB Output is correct
25 Correct 2466 ms 421996 KB Output is correct
26 Correct 2475 ms 827140 KB Output is correct
27 Correct 2387 ms 615992 KB Output is correct
28 Correct 1855 ms 570216 KB Output is correct
29 Correct 519 ms 216556 KB Output is correct
30 Correct 911 ms 237136 KB Output is correct
31 Correct 2031 ms 280512 KB Output is correct
32 Correct 2520 ms 625348 KB Output is correct
33 Correct 2513 ms 625092 KB Output is correct

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 201044 KB Output is correct
2 Correct 274 ms 201832 KB Output is correct
3 Correct 286 ms 201512 KB Output is correct
4 Correct 279 ms 201452 KB Output is correct
5 Correct 276 ms 202192 KB Output is correct
6 Correct 220 ms 200792 KB Output is correct
7 Correct 227 ms 200784 KB Output is correct
8 Correct 239 ms 200840 KB Output is correct
9 Correct 232 ms 200900 KB Output is correct
10 Correct 243 ms 200784 KB Output is correct
11 Correct 238 ms 201220 KB Output is correct
12 Correct 268 ms 201804 KB Output is correct
13 Correct 276 ms 202572 KB Output is correct
14 Correct 291 ms 202576 KB Output is correct
15 Correct 227 ms 200724 KB Output is correct
16 Correct 236 ms 200728 KB Output is correct
17 Correct 232 ms 200784 KB Output is correct
18 Execution timed out 3065 ms 313860 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 201044 KB Output is correct
2 Correct 274 ms 201832 KB Output is correct
3 Correct 286 ms 201512 KB Output is correct
4 Correct 279 ms 201452 KB Output is correct
5 Correct 276 ms 202192 KB Output is correct
6 Correct 220 ms 200792 KB Output is correct
7 Correct 227 ms 200784 KB Output is correct
8 Correct 239 ms 200840 KB Output is correct
9 Correct 232 ms 200900 KB Output is correct
10 Correct 243 ms 200784 KB Output is correct
11 Correct 238 ms 201220 KB Output is correct
12 Correct 268 ms 201804 KB Output is correct
13 Correct 276 ms 202572 KB Output is correct
14 Correct 291 ms 202576 KB Output is correct
15 Correct 227 ms 200724 KB Output is correct
16 Correct 236 ms 200728 KB Output is correct
17 Correct 232 ms 200784 KB Output is correct
18 Execution timed out 3065 ms 313860 KB Time limit exceeded
19 Halted 0 ms 0 KB -