oj.uz

Submission #678866

# Submission time Handle Problem Language Result Execution time Memory
678866 2023-01-06T19:18:20 Z qwerasdfzxcl Land of the Rainbow Gold (APIO17_rainbow) C++17
100 / 100
 661 ms 230492 KB 
#include "rainbow.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
constexpr int INF = 1e9+100;

struct Node{
    int l, r, x;
    Node(){}
    Node(int _l, int _r, int _x): l(_l), r(_r), x(_x) {}
};

struct PST{
    vector<Node> tree;
    vector<int> root;
    int sz;

    int cp(int x){
        tree.push_back(tree[x]);
        return (int)tree.size()-1;
    }
    void update(int i, int l, int r, int p, int x){
        tree[i].x += x;
        if (l==r) return;

        int m = (l+r)>>1;

        if (p <= m){
            tree[i].l = cp(tree[i].l);
            update(tree[i].l, l, m, p, x);
        }
        else{
            tree[i].r = cp(tree[i].r);
            update(tree[i].r, m+1, r, p, x);
        }
    }
    int query(int i, int l, int r, int s, int e){
        if (r<s || e<l) return 0;
        if (s<=l && r<=e) return tree[i].x;

        int m = (l+r)>>1;
        return query(tree[i].l, l, m, s, e) + query(tree[i].r, m+1, r, s, e);
    }

    void init(int n){
        sz = n;
        tree.emplace_back(0, 0, 0);
        root.push_back(0);
    }
    void add_root(){root.push_back(cp(root.back()));}
    void update(int p, int x){update(root.back(), 1, sz, p, x);}
    int query(int t, int l, int r){return query(root[t], 1, sz, l, r);}
    int query2D(int t1, int t2, int l, int r){return query(t2, l, r) - query(t1-1, l, r);}

}treeV, treeEh, treeEv, treeF;

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}, n, m, mnx, mxx, mny, mxy;
vector<int> V[200200], Eh[200200], Ev[200200], F[200200];

void add_vertex(int x, int y){
    mnx = min(mnx, x);
    mxx = max(mxx, x);
    mny = min(mny, y);
    mxy = max(mxy, y);

    V[x].push_back(y);

    Eh[x].push_back(y-1);
    Eh[x].push_back(y);
    Ev[x-1].push_back(y);
    Ev[x].push_back(y);

    for (int i=-1;i<=0;i++){
        for (int j=-1;j<=0;j++){
            F[x+i].push_back(y+j);
        }
    }
}

void pst_init(vector<int> a[], PST &tree){
    tree.init(m);
    for (int i=1;i<=n;i++){
        sort(a[i].begin(), a[i].end());
        a[i].erase(unique(a[i].begin(), a[i].end()), a[i].end());

        tree.add_root();
        for (auto &y:a[i]) if (y>0) tree.update(y, 1);
    }
}

void init(int R, int C, int sr, int sc, int M, char *S) {
    n = R, m = C;
    mnx = mny = 1e9;
    mxx = mxy = -1e9;
    add_vertex(sr, sc);

    for (int i=0;i<M;i++){
        int k;
        if (S[i]=='N') k = 0;
        if (S[i]=='E') k = 1;
        if (S[i]=='S') k = 2;
        if (S[i]=='W') k = 3;

        sr += dx[k], sc += dy[k];
        add_vertex(sr, sc);
    }

    pst_init(V, treeV);
    pst_init(Eh, treeEh);
    pst_init(Ev, treeEv);
    pst_init(F, treeF);
}


int colour(int ar, int ac, int br, int bc) {
    ll v = 0, e = 0, f = 0;
    if (ar < mnx && mxx < br && ac < mny && mxy < bc) f = 1;

    ll xL = br - ar, yL = bc - ac;

    v = xL * yL - treeV.query2D(ar, br, ac, bc);
    e = xL * (yL-1) - treeEh.query2D(ar, br, ac, bc-1);
    e += (xL-1) * yL - treeEv.query2D(ar, br-1, ac, bc);
    f += (xL-1) * (yL-1) - treeF.query2D(ar, br-1, ac, bc-1);

    return v - e + f;
}

Compilation message

rainbow.cpp: In function 'void init(int, int, int, int, int, char*)':
rainbow.cpp:105:32: warning: 'k' may be used uninitialized in this function [-Wmaybe-uninitialized]
  105 |         sr += dx[k], sc += dy[k];
      |                            ~~~~^

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19156 KB Output is correct
2 Correct 12 ms 19680 KB Output is correct
3 Correct 11 ms 19156 KB Output is correct
4 Correct 12 ms 19248 KB Output is correct
5 Correct 12 ms 19840 KB Output is correct
6 Correct 11 ms 19024 KB Output is correct
7 Correct 11 ms 19112 KB Output is correct
8 Correct 10 ms 19028 KB Output is correct
9 Correct 10 ms 19028 KB Output is correct
10 Correct 10 ms 19028 KB Output is correct
11 Correct 12 ms 19284 KB Output is correct
12 Correct 12 ms 19504 KB Output is correct
13 Correct 12 ms 19864 KB Output is correct
14 Correct 12 ms 20104 KB Output is correct
15 Correct 9 ms 18996 KB Output is correct
16 Correct 10 ms 18992 KB Output is correct
17 Correct 11 ms 19028 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 18992 KB Output is correct
2 Correct 11 ms 19028 KB Output is correct
3 Correct 416 ms 110384 KB Output is correct
4 Correct 507 ms 176744 KB Output is correct
5 Correct 535 ms 168920 KB Output is correct
6 Correct 436 ms 124884 KB Output is correct
7 Correct 449 ms 121152 KB Output is correct
8 Correct 293 ms 24412 KB Output is correct
9 Correct 522 ms 176188 KB Output is correct
10 Correct 510 ms 174708 KB Output is correct
11 Correct 442 ms 124880 KB Output is correct
12 Correct 248 ms 173408 KB Output is correct
13 Correct 302 ms 176460 KB Output is correct
14 Correct 260 ms 175072 KB Output is correct
15 Correct 215 ms 125204 KB Output is correct
16 Correct 436 ms 115180 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 18996 KB Output is correct
2 Correct 203 ms 209328 KB Output is correct
3 Correct 216 ms 226832 KB Output is correct
4 Correct 212 ms 212636 KB Output is correct
5 Correct 193 ms 192112 KB Output is correct
6 Correct 84 ms 72544 KB Output is correct
7 Correct 120 ms 107824 KB Output is correct
8 Correct 152 ms 130176 KB Output is correct
9 Correct 144 ms 121048 KB Output is correct
10 Correct 55 ms 49200 KB Output is correct
11 Correct 124 ms 106052 KB Output is correct
12 Correct 202 ms 209264 KB Output is correct
13 Correct 215 ms 226872 KB Output is correct
14 Correct 208 ms 212644 KB Output is correct
15 Correct 194 ms 192192 KB Output is correct
16 Correct 78 ms 67536 KB Output is correct
17 Correct 117 ms 108196 KB Output is correct
18 Correct 204 ms 210040 KB Output is correct
19 Correct 186 ms 193720 KB Output is correct
20 Correct 185 ms 193636 KB Output is correct
21 Correct 154 ms 130224 KB Output is correct
22 Correct 141 ms 121152 KB Output is correct
23 Correct 54 ms 49260 KB Output is correct
24 Correct 121 ms 106036 KB Output is correct
25 Correct 199 ms 209392 KB Output is correct
26 Correct 221 ms 226956 KB Output is correct
27 Correct 216 ms 212712 KB Output is correct
28 Correct 199 ms 192308 KB Output is correct
29 Correct 82 ms 67620 KB Output is correct
30 Correct 125 ms 108300 KB Output is correct
31 Correct 220 ms 210160 KB Output is correct
32 Correct 194 ms 193688 KB Output is correct
33 Correct 202 ms 193776 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19156 KB Output is correct
2 Correct 12 ms 19680 KB Output is correct
3 Correct 11 ms 19156 KB Output is correct
4 Correct 12 ms 19248 KB Output is correct
5 Correct 12 ms 19840 KB Output is correct
6 Correct 11 ms 19024 KB Output is correct
7 Correct 11 ms 19112 KB Output is correct
8 Correct 10 ms 19028 KB Output is correct
9 Correct 10 ms 19028 KB Output is correct
10 Correct 10 ms 19028 KB Output is correct
11 Correct 12 ms 19284 KB Output is correct
12 Correct 12 ms 19504 KB Output is correct
13 Correct 12 ms 19864 KB Output is correct
14 Correct 12 ms 20104 KB Output is correct
15 Correct 9 ms 18996 KB Output is correct
16 Correct 10 ms 18992 KB Output is correct
17 Correct 11 ms 19028 KB Output is correct
18 Correct 471 ms 75196 KB Output is correct
19 Correct 197 ms 24456 KB Output is correct
20 Correct 131 ms 22836 KB Output is correct
21 Correct 144 ms 23184 KB Output is correct
22 Correct 157 ms 23444 KB Output is correct
23 Correct 177 ms 24220 KB Output is correct
24 Correct 131 ms 23244 KB Output is correct
25 Correct 148 ms 23432 KB Output is correct
26 Correct 158 ms 23724 KB Output is correct
27 Correct 275 ms 71832 KB Output is correct
28 Correct 238 ms 43904 KB Output is correct
29 Correct 280 ms 62268 KB Output is correct
30 Correct 384 ms 107920 KB Output is correct
31 Correct 12 ms 19124 KB Output is correct
32 Correct 352 ms 63540 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19156 KB Output is correct
2 Correct 12 ms 19680 KB Output is correct
3 Correct 11 ms 19156 KB Output is correct
4 Correct 12 ms 19248 KB Output is correct
5 Correct 12 ms 19840 KB Output is correct
6 Correct 11 ms 19024 KB Output is correct
7 Correct 11 ms 19112 KB Output is correct
8 Correct 10 ms 19028 KB Output is correct
9 Correct 10 ms 19028 KB Output is correct
10 Correct 10 ms 19028 KB Output is correct
11 Correct 12 ms 19284 KB Output is correct
12 Correct 12 ms 19504 KB Output is correct
13 Correct 12 ms 19864 KB Output is correct
14 Correct 12 ms 20104 KB Output is correct
15 Correct 9 ms 18996 KB Output is correct
16 Correct 10 ms 18992 KB Output is correct
17 Correct 11 ms 19028 KB Output is correct
18 Correct 471 ms 75196 KB Output is correct
19 Correct 197 ms 24456 KB Output is correct
20 Correct 131 ms 22836 KB Output is correct
21 Correct 144 ms 23184 KB Output is correct
22 Correct 157 ms 23444 KB Output is correct
23 Correct 177 ms 24220 KB Output is correct
24 Correct 131 ms 23244 KB Output is correct
25 Correct 148 ms 23432 KB Output is correct
26 Correct 158 ms 23724 KB Output is correct
27 Correct 275 ms 71832 KB Output is correct
28 Correct 238 ms 43904 KB Output is correct
29 Correct 280 ms 62268 KB Output is correct
30 Correct 384 ms 107920 KB Output is correct
31 Correct 12 ms 19124 KB Output is correct
32 Correct 352 ms 63540 KB Output is correct
33 Correct 203 ms 209328 KB Output is correct
34 Correct 216 ms 226832 KB Output is correct
35 Correct 212 ms 212636 KB Output is correct
36 Correct 193 ms 192112 KB Output is correct
37 Correct 84 ms 72544 KB Output is correct
38 Correct 120 ms 107824 KB Output is correct
39 Correct 152 ms 130176 KB Output is correct
40 Correct 144 ms 121048 KB Output is correct
41 Correct 55 ms 49200 KB Output is correct
42 Correct 124 ms 106052 KB Output is correct
43 Correct 202 ms 209264 KB Output is correct
44 Correct 215 ms 226872 KB Output is correct
45 Correct 208 ms 212644 KB Output is correct
46 Correct 194 ms 192192 KB Output is correct
47 Correct 78 ms 67536 KB Output is correct
48 Correct 117 ms 108196 KB Output is correct
49 Correct 204 ms 210040 KB Output is correct
50 Correct 186 ms 193720 KB Output is correct
51 Correct 185 ms 193636 KB Output is correct
52 Correct 154 ms 130224 KB Output is correct
53 Correct 141 ms 121152 KB Output is correct
54 Correct 54 ms 49260 KB Output is correct
55 Correct 121 ms 106036 KB Output is correct
56 Correct 199 ms 209392 KB Output is correct
57 Correct 221 ms 226956 KB Output is correct
58 Correct 216 ms 212712 KB Output is correct
59 Correct 199 ms 192308 KB Output is correct
60 Correct 82 ms 67620 KB Output is correct
61 Correct 125 ms 108300 KB Output is correct
62 Correct 220 ms 210160 KB Output is correct
63 Correct 194 ms 193688 KB Output is correct
64 Correct 202 ms 193776 KB Output is correct
65 Correct 416 ms 110384 KB Output is correct
66 Correct 507 ms 176744 KB Output is correct
67 Correct 535 ms 168920 KB Output is correct
68 Correct 436 ms 124884 KB Output is correct
69 Correct 449 ms 121152 KB Output is correct
70 Correct 293 ms 24412 KB Output is correct
71 Correct 522 ms 176188 KB Output is correct
72 Correct 510 ms 174708 KB Output is correct
73 Correct 442 ms 124880 KB Output is correct
74 Correct 248 ms 173408 KB Output is correct
75 Correct 302 ms 176460 KB Output is correct
76 Correct 260 ms 175072 KB Output is correct
77 Correct 215 ms 125204 KB Output is correct
78 Correct 436 ms 115180 KB Output is correct
79 Correct 661 ms 133568 KB Output is correct
80 Correct 646 ms 124608 KB Output is correct
81 Correct 288 ms 52672 KB Output is correct
82 Correct 409 ms 109496 KB Output is correct
83 Correct 643 ms 212848 KB Output is correct
84 Correct 591 ms 230492 KB Output is correct
85 Correct 606 ms 216148 KB Output is correct
86 Correct 561 ms 195768 KB Output is correct
87 Correct 430 ms 71036 KB Output is correct
88 Correct 470 ms 111728 KB Output is correct
89 Correct 545 ms 213624 KB Output is correct
90 Correct 614 ms 197184 KB Output is correct
91 Correct 524 ms 197060 KB Output is correct