oj.uz

Submission #230222

# Submission time Handle Problem Language Result Execution time Memory
230222 2020-05-09T08:20:29 Z lyc Land of the Rainbow Gold (APIO17_rainbow) C++14
100 / 100
 1461 ms 179992 KB 
#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;

#define TRACE(x) cout << #x << " :: " << x << '\n'
#define _ << " " <<
#define FOR(i,a,b) for (int i=(a); i<=(b); ++i)
#define RFOR(i,a,b) for (int i=(a); i>=(b); --i)
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(), (x).end()

struct node {
    int s, e, m; vector<int> v;
    node *l, *r;
    node(int s, int e): s(s), e(e), m((s+e)/2) {
        if (s != e) l = new node(s,m), r = new node(m+1,e);
    }

    void add(int x, int z) {
        if (s == e) { v.push_back(z); return; }
        else if (x <= m) l->add(x,z);
        else r->add(x,z);
    }

    vector<int>& build() {
        if (s != e) {
            auto a = l->build(), b = r->build();
            for (int i = 0, j = 0; i < SZ(a) || j < SZ(b); ) {
                if (i < SZ(a) && (j == SZ(b) || a[i] < b[j])) v.push_back(a[i++]);
                else v.push_back(b[j++]);
            }
        }
        return v;
    }

    int query(int x, int y, int a, int b) {
        if (x > y || a > b) return 0;
        if (s == x && e == y) { return lower_bound(ALL(v),b+1)-lower_bound(ALL(v),a); }
        if (y <= m) return l->query(x,y,a,b);
        if (x > m) return r->query(x,y,a,b);
        return l->query(x,m,a,b) + r->query(m+1,y,a,b);
    }
} *grid, *horz, *vert, *face;

void init(int R, int C, int sr, int sc, int M, char *S) {
    grid = new node(1,R+1);
    horz = new node(1,R+1);
    vert = new node(1,R+1);
    face = new node(1,R+1);

    using ii = pair<int,int>;
    vector<ii> gset, vset, hset, fset;
    gset.emplace_back(sr,sc);
    vset.emplace_back(sr,sc);
    vset.emplace_back(sr+1,sc);
    hset.emplace_back(sr,sc);
    hset.emplace_back(sr,sc+1);
    fset.emplace_back(sr,sc);
    fset.emplace_back(sr+1,sc);
    fset.emplace_back(sr,sc+1);
    fset.emplace_back(sr+1,sc+1);
    FOR(i,0,M-1){
        switch (S[i]) {
            case 'N':
                --sr;
                break;
            case 'S':
                ++sr;
                break;
            case 'E':
                ++sc;
                break;
            case 'W':
                --sc;
                break;
        }
        gset.emplace_back(sr,sc);
        vset.emplace_back(sr,sc);
        vset.emplace_back(sr+1,sc);
        hset.emplace_back(sr,sc);
        hset.emplace_back(sr,sc+1);
        fset.emplace_back(sr,sc);
        fset.emplace_back(sr+1,sc);
        fset.emplace_back(sr,sc+1);
        fset.emplace_back(sr+1,sc+1);
    }

    sort(ALL(gset)); gset.resize(unique(ALL(gset))-gset.begin());
    sort(ALL(hset)); hset.resize(unique(ALL(hset))-hset.begin());
    sort(ALL(vset)); vset.resize(unique(ALL(vset))-vset.begin());
    sort(ALL(fset)); fset.resize(unique(ALL(fset))-fset.begin());
    for (auto& x : gset) grid->add(x.first,x.second);
    for (auto& x : hset) horz->add(x.first,x.second);
    for (auto& x : vset) vert->add(x.first,x.second);
    for (auto& x : fset) face->add(x.first,x.second);
    grid->build();
    horz->build();
    vert->build();
    face->build();
}

int colour(int ar, int ac, int br, int bc) {
    int vb = grid->query(ar,br,ac,bc);
    int conn = vb - grid->query(ar+1,br-1,ac+1,bc-1);

    long long v = (long long)(br-ar+1)*(bc-ac+1) - vb;
    if (v == 0) return 0;
    long long e = (long long)(br-ar+1)*(bc-ac) - horz->query(ar,br,ac+1,bc)
        + (long long)(br-ar)*(bc-ac+1) - vert->query(ar+1,br,ac,bc);
    long long f = (long long)(br-ar)*(bc-ac) - face->query(ar+1,br,ac+1,bc) + 1;

    if (vb > 0 && conn == 0) ++f;
    //TRACE(v _ e _ f _ vb _ conn);
    return v-e+f-1;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 384 KB Output is correct
2 Correct 9 ms 768 KB Output is correct
3 Correct 7 ms 512 KB Output is correct
4 Correct 7 ms 512 KB Output is correct
5 Correct 10 ms 824 KB Output is correct
6 Correct 4 ms 256 KB Output is correct
7 Correct 4 ms 256 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 4 ms 256 KB Output is correct
10 Correct 4 ms 384 KB Output is correct
11 Correct 8 ms 512 KB Output is correct
12 Correct 9 ms 640 KB Output is correct
13 Correct 10 ms 896 KB Output is correct
14 Correct 12 ms 1036 KB Output is correct
15 Correct 4 ms 256 KB Output is correct
16 Correct 5 ms 256 KB Output is correct
17 Correct 4 ms 256 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 4 ms 256 KB Output is correct
3 Correct 165 ms 10196 KB Output is correct
4 Correct 204 ms 16844 KB Output is correct
5 Correct 207 ms 16840 KB Output is correct
6 Correct 200 ms 14792 KB Output is correct
7 Correct 208 ms 14788 KB Output is correct
8 Correct 118 ms 8528 KB Output is correct
9 Correct 204 ms 16836 KB Output is correct
10 Correct 205 ms 16836 KB Output is correct
11 Correct 206 ms 14660 KB Output is correct
12 Correct 147 ms 16204 KB Output is correct
13 Correct 139 ms 16836 KB Output is correct
14 Correct 151 ms 16836 KB Output is correct
15 Correct 158 ms 14784 KB Output is correct
16 Correct 172 ms 13764 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct
2 Correct 233 ms 154780 KB Output is correct
3 Correct 361 ms 179772 KB Output is correct
4 Correct 328 ms 175556 KB Output is correct
5 Correct 276 ms 156228 KB Output is correct
6 Correct 198 ms 117988 KB Output is correct
7 Correct 214 ms 127940 KB Output is correct
8 Correct 87 ms 18880 KB Output is correct
9 Correct 106 ms 19524 KB Output is correct
10 Correct 112 ms 63572 KB Output is correct
11 Correct 173 ms 82168 KB Output is correct
12 Correct 230 ms 154824 KB Output is correct
13 Correct 362 ms 179724 KB Output is correct
14 Correct 328 ms 175556 KB Output is correct
15 Correct 282 ms 156088 KB Output is correct
16 Correct 191 ms 115908 KB Output is correct
17 Correct 225 ms 128200 KB Output is correct
18 Correct 260 ms 161604 KB Output is correct
19 Correct 291 ms 167496 KB Output is correct
20 Correct 291 ms 167620 KB Output is correct
21 Correct 89 ms 18884 KB Output is correct
22 Correct 104 ms 19524 KB Output is correct
23 Correct 112 ms 63572 KB Output is correct
24 Correct 191 ms 82116 KB Output is correct
25 Correct 232 ms 154824 KB Output is correct
26 Correct 356 ms 179652 KB Output is correct
27 Correct 326 ms 175556 KB Output is correct
28 Correct 279 ms 156052 KB Output is correct
29 Correct 191 ms 115908 KB Output is correct
30 Correct 222 ms 128320 KB Output is correct
31 Correct 267 ms 161476 KB Output is correct
32 Correct 289 ms 167488 KB Output is correct
33 Correct 294 ms 167616 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 384 KB Output is correct
2 Correct 9 ms 768 KB Output is correct
3 Correct 7 ms 512 KB Output is correct
4 Correct 7 ms 512 KB Output is correct
5 Correct 10 ms 824 KB Output is correct
6 Correct 4 ms 256 KB Output is correct
7 Correct 4 ms 256 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 4 ms 256 KB Output is correct
10 Correct 4 ms 384 KB Output is correct
11 Correct 8 ms 512 KB Output is correct
12 Correct 9 ms 640 KB Output is correct
13 Correct 10 ms 896 KB Output is correct
14 Correct 12 ms 1036 KB Output is correct
15 Correct 4 ms 256 KB Output is correct
16 Correct 5 ms 256 KB Output is correct
17 Correct 4 ms 256 KB Output is correct
18 Correct 1257 ms 25924 KB Output is correct
19 Correct 249 ms 4600 KB Output is correct
20 Correct 231 ms 4092 KB Output is correct
21 Correct 263 ms 4220 KB Output is correct
22 Correct 291 ms 4472 KB Output is correct
23 Correct 241 ms 4764 KB Output is correct
24 Correct 298 ms 4276 KB Output is correct
25 Correct 298 ms 4368 KB Output is correct
26 Correct 314 ms 4740 KB Output is correct
27 Correct 602 ms 22984 KB Output is correct
28 Correct 513 ms 14788 KB Output is correct
29 Correct 564 ms 20804 KB Output is correct
30 Correct 1000 ms 42180 KB Output is correct
31 Correct 8 ms 384 KB Output is correct
32 Correct 1002 ms 22596 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 384 KB Output is correct
2 Correct 9 ms 768 KB Output is correct
3 Correct 7 ms 512 KB Output is correct
4 Correct 7 ms 512 KB Output is correct
5 Correct 10 ms 824 KB Output is correct
6 Correct 4 ms 256 KB Output is correct
7 Correct 4 ms 256 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 4 ms 256 KB Output is correct
10 Correct 4 ms 384 KB Output is correct
11 Correct 8 ms 512 KB Output is correct
12 Correct 9 ms 640 KB Output is correct
13 Correct 10 ms 896 KB Output is correct
14 Correct 12 ms 1036 KB Output is correct
15 Correct 4 ms 256 KB Output is correct
16 Correct 5 ms 256 KB Output is correct
17 Correct 4 ms 256 KB Output is correct
18 Correct 1257 ms 25924 KB Output is correct
19 Correct 249 ms 4600 KB Output is correct
20 Correct 231 ms 4092 KB Output is correct
21 Correct 263 ms 4220 KB Output is correct
22 Correct 291 ms 4472 KB Output is correct
23 Correct 241 ms 4764 KB Output is correct
24 Correct 298 ms 4276 KB Output is correct
25 Correct 298 ms 4368 KB Output is correct
26 Correct 314 ms 4740 KB Output is correct
27 Correct 602 ms 22984 KB Output is correct
28 Correct 513 ms 14788 KB Output is correct
29 Correct 564 ms 20804 KB Output is correct
30 Correct 1000 ms 42180 KB Output is correct
31 Correct 8 ms 384 KB Output is correct
32 Correct 1002 ms 22596 KB Output is correct
33 Correct 233 ms 154780 KB Output is correct
34 Correct 361 ms 179772 KB Output is correct
35 Correct 328 ms 175556 KB Output is correct
36 Correct 276 ms 156228 KB Output is correct
37 Correct 198 ms 117988 KB Output is correct
38 Correct 214 ms 127940 KB Output is correct
39 Correct 87 ms 18880 KB Output is correct
40 Correct 106 ms 19524 KB Output is correct
41 Correct 112 ms 63572 KB Output is correct
42 Correct 173 ms 82168 KB Output is correct
43 Correct 230 ms 154824 KB Output is correct
44 Correct 362 ms 179724 KB Output is correct
45 Correct 328 ms 175556 KB Output is correct
46 Correct 282 ms 156088 KB Output is correct
47 Correct 191 ms 115908 KB Output is correct
48 Correct 225 ms 128200 KB Output is correct
49 Correct 260 ms 161604 KB Output is correct
50 Correct 291 ms 167496 KB Output is correct
51 Correct 291 ms 167620 KB Output is correct
52 Correct 89 ms 18884 KB Output is correct
53 Correct 104 ms 19524 KB Output is correct
54 Correct 112 ms 63572 KB Output is correct
55 Correct 191 ms 82116 KB Output is correct
56 Correct 232 ms 154824 KB Output is correct
57 Correct 356 ms 179652 KB Output is correct
58 Correct 326 ms 175556 KB Output is correct
59 Correct 279 ms 156052 KB Output is correct
60 Correct 191 ms 115908 KB Output is correct
61 Correct 222 ms 128320 KB Output is correct
62 Correct 267 ms 161476 KB Output is correct
63 Correct 289 ms 167488 KB Output is correct
64 Correct 294 ms 167616 KB Output is correct
65 Correct 364 ms 19008 KB Output is correct
66 Correct 467 ms 19652 KB Output is correct
67 Correct 509 ms 64108 KB Output is correct
68 Correct 702 ms 82372 KB Output is correct
69 Correct 990 ms 155052 KB Output is correct
70 Correct 1461 ms 179992 KB Output is correct
71 Correct 1181 ms 175812 KB Output is correct
72 Correct 1169 ms 156228 KB Output is correct
73 Correct 902 ms 116068 KB Output is correct
74 Correct 899 ms 128328 KB Output is correct
75 Correct 937 ms 161600 KB Output is correct
76 Correct 1260 ms 167752 KB Output is correct
77 Correct 1179 ms 167744 KB Output is correct
78 Correct 165 ms 10196 KB Output is correct
79 Correct 204 ms 16844 KB Output is correct
80 Correct 207 ms 16840 KB Output is correct
81 Correct 200 ms 14792 KB Output is correct
82 Correct 208 ms 14788 KB Output is correct
83 Correct 118 ms 8528 KB Output is correct
84 Correct 204 ms 16836 KB Output is correct
85 Correct 205 ms 16836 KB Output is correct
86 Correct 206 ms 14660 KB Output is correct
87 Correct 147 ms 16204 KB Output is correct
88 Correct 139 ms 16836 KB Output is correct
89 Correct 151 ms 16836 KB Output is correct
90 Correct 158 ms 14784 KB Output is correct
91 Correct 172 ms 13764 KB Output is correct