oj.uz

Submission #1090070

# Submission time Handle Problem Language Result Execution time Memory
1090070 2024-09-17T16:57:38 Z alexander707070 Land of the Rainbow Gold (APIO17_rainbow) C++14
74 / 100
 3000 ms 830740 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+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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 257 ms 201072 KB Output is correct
2 Correct 272 ms 201988 KB Output is correct
3 Correct 265 ms 201580 KB Output is correct
4 Correct 266 ms 201292 KB Output is correct
5 Correct 281 ms 202200 KB Output is correct
6 Correct 240 ms 200772 KB Output is correct
7 Correct 272 ms 200788 KB Output is correct
8 Correct 221 ms 200756 KB Output is correct
9 Correct 226 ms 200780 KB Output is correct
10 Correct 229 ms 200836 KB Output is correct
11 Correct 247 ms 201296 KB Output is correct
12 Correct 270 ms 201604 KB Output is correct
13 Correct 272 ms 202496 KB Output is correct
14 Correct 290 ms 202800 KB Output is correct
15 Correct 220 ms 200784 KB Output is correct
16 Correct 213 ms 200784 KB Output is correct
17 Correct 209 ms 200792 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 200784 KB Output is correct
2 Correct 209 ms 200792 KB Output is correct
3 Correct 1636 ms 341452 KB Output is correct
4 Correct 2511 ms 425528 KB Output is correct
5 Correct 2417 ms 413336 KB Output is correct
6 Correct 1935 ms 332088 KB Output is correct
7 Correct 2017 ms 331984 KB Output is correct
8 Correct 287 ms 204372 KB Output is correct
9 Correct 2506 ms 425604 KB Output is correct
10 Correct 2470 ms 413336 KB Output is correct
11 Correct 1951 ms 331976 KB Output is correct
12 Correct 2377 ms 413080 KB Output is correct
13 Correct 2390 ms 425528 KB Output is correct
14 Correct 2375 ms 413324 KB Output is correct
15 Correct 1964 ms 331904 KB Output is correct
16 Correct 1838 ms 361568 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 200784 KB Output is correct
2 Correct 2501 ms 422068 KB Output is correct
3 Correct 2364 ms 827216 KB Output is correct
4 Correct 2345 ms 616204 KB Output is correct
5 Correct 1774 ms 570292 KB Output is correct
6 Correct 578 ms 220748 KB Output is correct
7 Correct 982 ms 236664 KB Output is correct
8 Correct 2127 ms 332260 KB Output is correct
9 Correct 1917 ms 312296 KB Output is correct
10 Correct 622 ms 219840 KB Output is correct
11 Correct 1267 ms 310052 KB Output is correct
12 Correct 2488 ms 421992 KB Output is correct
13 Correct 2321 ms 827456 KB Output is correct
14 Correct 2287 ms 616292 KB Output is correct
15 Correct 1834 ms 570216 KB Output is correct
16 Correct 556 ms 216656 KB Output is correct
17 Correct 918 ms 237120 KB Output is correct
18 Correct 2048 ms 280536 KB Output is correct
19 Correct 2533 ms 625332 KB Output is correct
20 Correct 2422 ms 625120 KB Output is correct
21 Correct 2184 ms 332212 KB Output is correct
22 Correct 1889 ms 312368 KB Output is correct
23 Correct 610 ms 219728 KB Output is correct
24 Correct 1297 ms 310228 KB Output is correct
25 Correct 2443 ms 422096 KB Output is correct
26 Correct 2374 ms 827084 KB Output is correct
27 Correct 2345 ms 616000 KB Output is correct
28 Correct 1824 ms 570244 KB Output is correct
29 Correct 546 ms 216656 KB Output is correct
30 Correct 974 ms 237140 KB Output is correct
31 Correct 2130 ms 280544 KB Output is correct
32 Correct 2477 ms 625272 KB Output is correct
33 Correct 2341 ms 625060 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 257 ms 201072 KB Output is correct
2 Correct 272 ms 201988 KB Output is correct
3 Correct 265 ms 201580 KB Output is correct
4 Correct 266 ms 201292 KB Output is correct
5 Correct 281 ms 202200 KB Output is correct
6 Correct 240 ms 200772 KB Output is correct
7 Correct 272 ms 200788 KB Output is correct
8 Correct 221 ms 200756 KB Output is correct
9 Correct 226 ms 200780 KB Output is correct
10 Correct 229 ms 200836 KB Output is correct
11 Correct 247 ms 201296 KB Output is correct
12 Correct 270 ms 201604 KB Output is correct
13 Correct 272 ms 202496 KB Output is correct
14 Correct 290 ms 202800 KB Output is correct
15 Correct 220 ms 200784 KB Output is correct
16 Correct 213 ms 200784 KB Output is correct
17 Correct 209 ms 200792 KB Output is correct
18 Correct 2255 ms 296016 KB Output is correct
19 Correct 537 ms 208720 KB Output is correct
20 Correct 630 ms 205312 KB Output is correct
21 Correct 562 ms 206292 KB Output is correct
22 Correct 590 ms 207952 KB Output is correct
23 Correct 535 ms 208384 KB Output is correct
24 Correct 522 ms 205676 KB Output is correct
25 Correct 547 ms 206424 KB Output is correct
26 Correct 635 ms 208056 KB Output is correct
27 Correct 1337 ms 247844 KB Output is correct
28 Correct 919 ms 225044 KB Output is correct
29 Correct 1317 ms 238420 KB Output is correct
30 Correct 2529 ms 283976 KB Output is correct
31 Correct 213 ms 201128 KB Output is correct
32 Correct 1582 ms 243280 KB Output is correct

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 257 ms 201072 KB Output is correct
2 Correct 272 ms 201988 KB Output is correct
3 Correct 265 ms 201580 KB Output is correct
4 Correct 266 ms 201292 KB Output is correct
5 Correct 281 ms 202200 KB Output is correct
6 Correct 240 ms 200772 KB Output is correct
7 Correct 272 ms 200788 KB Output is correct
8 Correct 221 ms 200756 KB Output is correct
9 Correct 226 ms 200780 KB Output is correct
10 Correct 229 ms 200836 KB Output is correct
11 Correct 247 ms 201296 KB Output is correct
12 Correct 270 ms 201604 KB Output is correct
13 Correct 272 ms 202496 KB Output is correct
14 Correct 290 ms 202800 KB Output is correct
15 Correct 220 ms 200784 KB Output is correct
16 Correct 213 ms 200784 KB Output is correct
17 Correct 209 ms 200792 KB Output is correct
18 Correct 2255 ms 296016 KB Output is correct
19 Correct 537 ms 208720 KB Output is correct
20 Correct 630 ms 205312 KB Output is correct
21 Correct 562 ms 206292 KB Output is correct
22 Correct 590 ms 207952 KB Output is correct
23 Correct 535 ms 208384 KB Output is correct
24 Correct 522 ms 205676 KB Output is correct
25 Correct 547 ms 206424 KB Output is correct
26 Correct 635 ms 208056 KB Output is correct
27 Correct 1337 ms 247844 KB Output is correct
28 Correct 919 ms 225044 KB Output is correct
29 Correct 1317 ms 238420 KB Output is correct
30 Correct 2529 ms 283976 KB Output is correct
31 Correct 213 ms 201128 KB Output is correct
32 Correct 1582 ms 243280 KB Output is correct
33 Correct 2501 ms 422068 KB Output is correct
34 Correct 2364 ms 827216 KB Output is correct
35 Correct 2345 ms 616204 KB Output is correct
36 Correct 1774 ms 570292 KB Output is correct
37 Correct 578 ms 220748 KB Output is correct
38 Correct 982 ms 236664 KB Output is correct
39 Correct 2127 ms 332260 KB Output is correct
40 Correct 1917 ms 312296 KB Output is correct
41 Correct 622 ms 219840 KB Output is correct
42 Correct 1267 ms 310052 KB Output is correct
43 Correct 2488 ms 421992 KB Output is correct
44 Correct 2321 ms 827456 KB Output is correct
45 Correct 2287 ms 616292 KB Output is correct
46 Correct 1834 ms 570216 KB Output is correct
47 Correct 556 ms 216656 KB Output is correct
48 Correct 918 ms 237120 KB Output is correct
49 Correct 2048 ms 280536 KB Output is correct
50 Correct 2533 ms 625332 KB Output is correct
51 Correct 2422 ms 625120 KB Output is correct
52 Correct 2184 ms 332212 KB Output is correct
53 Correct 1889 ms 312368 KB Output is correct
54 Correct 610 ms 219728 KB Output is correct
55 Correct 1297 ms 310228 KB Output is correct
56 Correct 2443 ms 422096 KB Output is correct
57 Correct 2374 ms 827084 KB Output is correct
58 Correct 2345 ms 616000 KB Output is correct
59 Correct 1824 ms 570244 KB Output is correct
60 Correct 546 ms 216656 KB Output is correct
61 Correct 974 ms 237140 KB Output is correct
62 Correct 2130 ms 280544 KB Output is correct
63 Correct 2477 ms 625272 KB Output is correct
64 Correct 2341 ms 625060 KB Output is correct
65 Correct 1636 ms 341452 KB Output is correct
66 Correct 2511 ms 425528 KB Output is correct
67 Correct 2417 ms 413336 KB Output is correct
68 Correct 1935 ms 332088 KB Output is correct
69 Correct 2017 ms 331984 KB Output is correct
70 Correct 287 ms 204372 KB Output is correct
71 Correct 2506 ms 425604 KB Output is correct
72 Correct 2470 ms 413336 KB Output is correct
73 Correct 1951 ms 331976 KB Output is correct
74 Correct 2377 ms 413080 KB Output is correct
75 Correct 2390 ms 425528 KB Output is correct
76 Correct 2375 ms 413324 KB Output is correct
77 Correct 1964 ms 331904 KB Output is correct
78 Correct 1838 ms 361568 KB Output is correct
79 Correct 2368 ms 335608 KB Output is correct
80 Correct 2288 ms 315880 KB Output is correct
81 Correct 924 ms 223316 KB Output is correct
82 Correct 1793 ms 313472 KB Output is correct
83 Correct 2942 ms 425592 KB Output is correct
84 Correct 2805 ms 830740 KB Output is correct
85 Correct 2774 ms 619576 KB Output is correct
86 Correct 2503 ms 573880 KB Output is correct
87 Correct 964 ms 219984 KB Output is correct
88 Correct 1354 ms 240628 KB Output is correct
89 Correct 2496 ms 284032 KB Output is correct
90 Execution timed out 3084 ms 628852 KB Time limit exceeded
91 Halted 0 ms 0 KB -