oj.uz

Submission #155898

# Submission time Handle Problem Language Result Execution time Memory
155898 2019-10-02T00:04:29 Z mhy908 Land of the Rainbow Gold (APIO17_rainbow) C++14
100 / 100
 1975 ms 223260 KB 
#include "rainbow.h"
#include <bits/stdc++.h>
#define pb push_back
#define all(t) t.begin(), t.end()
using namespace std;
typedef long long LL;
struct MERGE_SORT_TREE {
    struct NODE {
        int st, fin;
        vector<int> vc;
    };
    NODE tree[1000010];
    int x;
    void initt(int point, int num){
        if(num==1){
            x++;
            tree[point].st=x;
            tree[point].fin=x;
        }
        if(num<=1)return;
        initt(point*2, num-num/2);
        initt(point*2+1, num/2);
        tree[point].st=tree[point*2].st;
        tree[point].fin=tree[point*2+1].fin;
    }
    void in_MST(int point, int num, int p) {
        tree[point].vc.pb(p);
        if(tree[point].st==tree[point].fin)return;
        int mid=(tree[point].st+tree[point].fin)/2;
        if(num<=mid)in_MST(point*2, num, p);
        else in_MST(point*2+1, num, p);
    }
    void relax(int point){
        sort(all(tree[point].vc));
        if(tree[point].st==tree[point].fin)return;
        relax(point*2);
        relax(point*2+1);
    }
    int sumrange(int point, int xl, int xr, int yl, int yr){
        int ret;
        if(tree[point].st>=xl&&tree[point].fin<=xr)
            return ret=upper_bound(all(tree[point].vc), yr)-lower_bound(all(tree[point].vc), yl);
        if(tree[point].st>xr||tree[point].fin<xl)return 0;
        return sumrange(point*2, xl, xr, yl, yr)+sumrange(point*2+1, xl, xr, yl, yr);
    }
    MERGE_SORT_TREE(){x=0; initt(1, 200010);}
    void update(LL num, LL p){
        in_MST(1, (int)num, (int)p);
    }
    int get_sum(int xl, int yl, int xr, int yr){
        if(xl>xr||yl>yr)return 0;
        return sumrange(1, xl, xr, yl, yr);
    }
};
MERGE_SORT_TREE segv, segdown, segright, segreal;
int n, m;
unordered_set<LL> s1, s2, s3, s4;
void inseg(int xx, int yy)
{
    LL x=(LL)xx, y=(LL)yy;
    if(!s1.count(300000*x+y)){
        s1.insert(300000*x+y);
        segv.update(x, y);
    }
    x++;
    if(!s1.count(300000*x+y)){
        s1.insert(300000*x+y);
        segv.update(x, y);
    }
    x--;
    y++;
    if(!s1.count(300000*x+y)){
        s1.insert(300000*x+y);
        segv.update(x, y);
    }
    x++;
    if(!s1.count(300000*x+y)){
        s1.insert(300000*x+y);
        segv.update(x, y);
    }
    x--;
    y--;
    if(!s2.count(300000*x+y)){
        s2.insert(300000*x+y);
        segdown.update(x, y);
    }
    y++;
    if(!s2.count(300000*x+y)){
        s2.insert(300000*x+y);
        segdown.update(x, y);
    }
    y--;
    if(!s3.count(300000*x+y)){
        s3.insert(300000*x+y);
        segright.update(x, y);
    }
    x++;
    if(!s3.count(300000*x+y)){
        s3.insert(300000*x+y);
        segright.update(x, y);
    }
    x--;
    if(!s4.count(300000*x+y)){
        s4.insert(300000*x+y);
        segreal.update(x, y);
    }
}
void init(int R, int C, int sr, int sc, int M, char S[]){
    n=R;
    m=C;
    inseg(sr, sc);
    for(int i=0; i<M; i++){
        if(S[i]=='N')sr--;
        if(S[i]=='S')sr++;
        if(S[i]=='W')sc--;
        if(S[i]=='E')sc++;
        inseg(sr, sc);
    }
    segreal.relax(1);
    segv.relax(1);
    segdown.relax(1);
    segright.relax(1);
}
int colour(int xst, int yst, int xfin, int yfin){
    int realv=segreal.get_sum(xst, yst, xfin, yfin);
    int v=segv.get_sum(xst+1, yst+1, xfin, yfin)+2*(xfin-xst+yfin-yst+2);
    int e=segdown.get_sum(xst, yst+1, xfin, yfin)+segright.get_sum(xst+1, yst, xfin, yfin)+2*(xfin-xst+yfin-yst+2);
    int c;
    if(!realv)c=1;
    else if(segreal.get_sum(xst, yst, xst, yfin)||segreal.get_sum(xfin, yst, xfin, yfin)||segreal.get_sum(xst, yst, xfin, yst)||segreal.get_sum(xst, yfin, xfin, yfin))c=1;
    else c=2;
    return e-v+c-realv;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 125816 KB Output is correct
2 Correct 142 ms 126328 KB Output is correct
3 Correct 139 ms 125832 KB Output is correct
4 Correct 141 ms 125816 KB Output is correct
5 Correct 143 ms 126484 KB Output is correct
6 Correct 135 ms 125604 KB Output is correct
7 Correct 135 ms 125692 KB Output is correct
8 Correct 135 ms 125560 KB Output is correct
9 Correct 134 ms 125660 KB Output is correct
10 Correct 134 ms 125560 KB Output is correct
11 Correct 139 ms 125856 KB Output is correct
12 Correct 141 ms 126116 KB Output is correct
13 Correct 157 ms 126848 KB Output is correct
14 Correct 169 ms 126968 KB Output is correct
15 Correct 191 ms 125584 KB Output is correct
16 Correct 135 ms 125560 KB Output is correct
17 Correct 157 ms 125576 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 125560 KB Output is correct
2 Correct 157 ms 125576 KB Output is correct
3 Correct 697 ms 170752 KB Output is correct
4 Correct 903 ms 200580 KB Output is correct
5 Correct 933 ms 200532 KB Output is correct
6 Correct 758 ms 184836 KB Output is correct
7 Correct 759 ms 184188 KB Output is correct
8 Correct 270 ms 129276 KB Output is correct
9 Correct 913 ms 200332 KB Output is correct
10 Correct 951 ms 200540 KB Output is correct
11 Correct 774 ms 185120 KB Output is correct
12 Correct 755 ms 196308 KB Output is correct
13 Correct 813 ms 200596 KB Output is correct
14 Correct 881 ms 200312 KB Output is correct
15 Correct 735 ms 185032 KB Output is correct
16 Correct 710 ms 184364 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 125584 KB Output is correct
2 Correct 664 ms 197200 KB Output is correct
3 Correct 977 ms 219880 KB Output is correct
4 Correct 918 ms 214868 KB Output is correct
5 Correct 779 ms 191824 KB Output is correct
6 Correct 343 ms 140996 KB Output is correct
7 Correct 436 ms 154724 KB Output is correct
8 Correct 1300 ms 190060 KB Output is correct
9 Correct 1180 ms 183164 KB Output is correct
10 Correct 387 ms 141064 KB Output is correct
11 Correct 647 ms 162324 KB Output is correct
12 Correct 671 ms 197180 KB Output is correct
13 Correct 994 ms 219796 KB Output is correct
14 Correct 932 ms 214924 KB Output is correct
15 Correct 804 ms 191692 KB Output is correct
16 Correct 271 ms 137740 KB Output is correct
17 Correct 449 ms 155688 KB Output is correct
18 Correct 920 ms 200500 KB Output is correct
19 Correct 843 ms 208872 KB Output is correct
20 Correct 850 ms 208636 KB Output is correct
21 Correct 1335 ms 190044 KB Output is correct
22 Correct 1127 ms 183348 KB Output is correct
23 Correct 350 ms 140964 KB Output is correct
24 Correct 643 ms 162192 KB Output is correct
25 Correct 658 ms 197120 KB Output is correct
26 Correct 995 ms 220020 KB Output is correct
27 Correct 897 ms 214756 KB Output is correct
28 Correct 780 ms 191888 KB Output is correct
29 Correct 264 ms 137692 KB Output is correct
30 Correct 447 ms 155456 KB Output is correct
31 Correct 1006 ms 200732 KB Output is correct
32 Correct 830 ms 208776 KB Output is correct
33 Correct 957 ms 208732 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 125816 KB Output is correct
2 Correct 142 ms 126328 KB Output is correct
3 Correct 139 ms 125832 KB Output is correct
4 Correct 141 ms 125816 KB Output is correct
5 Correct 143 ms 126484 KB Output is correct
6 Correct 135 ms 125604 KB Output is correct
7 Correct 135 ms 125692 KB Output is correct
8 Correct 135 ms 125560 KB Output is correct
9 Correct 134 ms 125660 KB Output is correct
10 Correct 134 ms 125560 KB Output is correct
11 Correct 139 ms 125856 KB Output is correct
12 Correct 141 ms 126116 KB Output is correct
13 Correct 157 ms 126848 KB Output is correct
14 Correct 169 ms 126968 KB Output is correct
15 Correct 191 ms 125584 KB Output is correct
16 Correct 135 ms 125560 KB Output is correct
17 Correct 157 ms 125576 KB Output is correct
18 Correct 1480 ms 169560 KB Output is correct
19 Correct 398 ms 131052 KB Output is correct
20 Correct 358 ms 129400 KB Output is correct
21 Correct 375 ms 129708 KB Output is correct
22 Correct 392 ms 130196 KB Output is correct
23 Correct 372 ms 130972 KB Output is correct
24 Correct 423 ms 129784 KB Output is correct
25 Correct 410 ms 130168 KB Output is correct
26 Correct 419 ms 130468 KB Output is correct
27 Correct 834 ms 160476 KB Output is correct
28 Correct 735 ms 144660 KB Output is correct
29 Correct 843 ms 158024 KB Output is correct
30 Correct 1694 ms 204088 KB Output is correct
31 Correct 138 ms 125688 KB Output is correct
32 Correct 1160 ms 161488 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 125816 KB Output is correct
2 Correct 142 ms 126328 KB Output is correct
3 Correct 139 ms 125832 KB Output is correct
4 Correct 141 ms 125816 KB Output is correct
5 Correct 143 ms 126484 KB Output is correct
6 Correct 135 ms 125604 KB Output is correct
7 Correct 135 ms 125692 KB Output is correct
8 Correct 135 ms 125560 KB Output is correct
9 Correct 134 ms 125660 KB Output is correct
10 Correct 134 ms 125560 KB Output is correct
11 Correct 139 ms 125856 KB Output is correct
12 Correct 141 ms 126116 KB Output is correct
13 Correct 157 ms 126848 KB Output is correct
14 Correct 169 ms 126968 KB Output is correct
15 Correct 191 ms 125584 KB Output is correct
16 Correct 135 ms 125560 KB Output is correct
17 Correct 157 ms 125576 KB Output is correct
18 Correct 1480 ms 169560 KB Output is correct
19 Correct 398 ms 131052 KB Output is correct
20 Correct 358 ms 129400 KB Output is correct
21 Correct 375 ms 129708 KB Output is correct
22 Correct 392 ms 130196 KB Output is correct
23 Correct 372 ms 130972 KB Output is correct
24 Correct 423 ms 129784 KB Output is correct
25 Correct 410 ms 130168 KB Output is correct
26 Correct 419 ms 130468 KB Output is correct
27 Correct 834 ms 160476 KB Output is correct
28 Correct 735 ms 144660 KB Output is correct
29 Correct 843 ms 158024 KB Output is correct
30 Correct 1694 ms 204088 KB Output is correct
31 Correct 138 ms 125688 KB Output is correct
32 Correct 1160 ms 161488 KB Output is correct
33 Correct 664 ms 197200 KB Output is correct
34 Correct 977 ms 219880 KB Output is correct
35 Correct 918 ms 214868 KB Output is correct
36 Correct 779 ms 191824 KB Output is correct
37 Correct 343 ms 140996 KB Output is correct
38 Correct 436 ms 154724 KB Output is correct
39 Correct 1300 ms 190060 KB Output is correct
40 Correct 1180 ms 183164 KB Output is correct
41 Correct 387 ms 141064 KB Output is correct
42 Correct 647 ms 162324 KB Output is correct
43 Correct 671 ms 197180 KB Output is correct
44 Correct 994 ms 219796 KB Output is correct
45 Correct 932 ms 214924 KB Output is correct
46 Correct 804 ms 191692 KB Output is correct
47 Correct 271 ms 137740 KB Output is correct
48 Correct 449 ms 155688 KB Output is correct
49 Correct 920 ms 200500 KB Output is correct
50 Correct 843 ms 208872 KB Output is correct
51 Correct 850 ms 208636 KB Output is correct
52 Correct 1335 ms 190044 KB Output is correct
53 Correct 1127 ms 183348 KB Output is correct
54 Correct 350 ms 140964 KB Output is correct
55 Correct 643 ms 162192 KB Output is correct
56 Correct 658 ms 197120 KB Output is correct
57 Correct 995 ms 220020 KB Output is correct
58 Correct 897 ms 214756 KB Output is correct
59 Correct 780 ms 191888 KB Output is correct
60 Correct 264 ms 137692 KB Output is correct
61 Correct 447 ms 155456 KB Output is correct
62 Correct 1006 ms 200732 KB Output is correct
63 Correct 830 ms 208776 KB Output is correct
64 Correct 957 ms 208732 KB Output is correct
65 Correct 1608 ms 193424 KB Output is correct
66 Correct 1541 ms 186768 KB Output is correct
67 Correct 809 ms 144380 KB Output is correct
68 Correct 1282 ms 165732 KB Output is correct
69 Correct 1321 ms 200788 KB Output is correct
70 Correct 1975 ms 223260 KB Output is correct
71 Correct 1576 ms 218472 KB Output is correct
72 Correct 1504 ms 195240 KB Output is correct
73 Correct 924 ms 141412 KB Output is correct
74 Correct 982 ms 158844 KB Output is correct
75 Correct 1395 ms 204212 KB Output is correct
76 Correct 1799 ms 212332 KB Output is correct
77 Correct 1628 ms 212200 KB Output is correct
78 Correct 697 ms 170752 KB Output is correct
79 Correct 903 ms 200580 KB Output is correct
80 Correct 933 ms 200532 KB Output is correct
81 Correct 758 ms 184836 KB Output is correct
82 Correct 759 ms 184188 KB Output is correct
83 Correct 270 ms 129276 KB Output is correct
84 Correct 913 ms 200332 KB Output is correct
85 Correct 951 ms 200540 KB Output is correct
86 Correct 774 ms 185120 KB Output is correct
87 Correct 755 ms 196308 KB Output is correct
88 Correct 813 ms 200596 KB Output is correct
89 Correct 881 ms 200312 KB Output is correct
90 Correct 735 ms 185032 KB Output is correct
91 Correct 710 ms 184364 KB Output is correct