oj.uz

Submission #172663

# Submission time Handle Problem Language Result Execution time Memory
172663 2020-01-02T09:58:17 Z dolphingarlic Land of the Rainbow Gold (APIO17_rainbow) C++14
100 / 100
 1380 ms 205748 KB 
/*
APIO 2017 Rainbow
- We can view a rectangle as a planar graph
    - Put temporary rivers on the outside of the rectangle
    - Each river segment is a node and adjacent rivers constitute an edge
- This problem then becomes finding the number of faces of a planar graph
- We can solve this with Euler's formula
- By Euler's formula, we have
    F = E - V + 1 + C
  where F is faces, E is edges, V is vertices, and C is the number of components
- Each corner of a square is a vertex and each side of a square is an edge if it has a river
*/
 
#include "rainbow.h"
#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
using namespace std;

const int MAXN = 2e5, MAXSEG = (6e5 + 9) * 19 + 1;

int cnt = 1, segtree[MAXSEG], left_c[MAXSEG], right_c[MAXSEG];

struct Segtree {
    set<int> data[MAXN + 1];
    int roots[MAXN + 2];

    void add(int x, int y) { data[x].insert(y); }

    void build() {
        FOR(i, 1, MAXN + 1) {
            roots[i + 1] = roots[i];
            for (int j : data[i]) update(j, roots[i + 1]);
        }
    }

    void update(int pos, int &node, int l = 1, int r = MAXN) {
        segtree[cnt] = segtree[node] + 1;
        left_c[cnt] = left_c[node];
        right_c[cnt] = right_c[node];
        node = cnt++;

        if (l == r) return;
        int mid = (l + r) / 2;
        if (pos > mid) update(pos, right_c[node], mid + 1, r);
        else update(pos, left_c[node], l, mid);
    }

    int query(int l1, int r1, int l2, int r2) {
        if (l2 > r2) return 0;
        return query(l2, r2, roots[r1 + 1], 1, MAXN) - query(l2, r2, roots[l1], 1, MAXN);
    }
    int query(int a, int b, int node, int l, int r) {
        if (a > r || b < l) return 0;
        if (a <= l && b >= r) return segtree[node];
        int mid = (l + r) / 2;
        return query(a, b, left_c[node], l, mid) + query(a, b, right_c[node], mid + 1, r);
    }
} vertices, edges_horiz, edges_vert, rivers;

int mx_r, mn_r, mx_c, mn_c;
 
void add_river(int x, int y) {
    vertices.add(x, y);
    vertices.add(x + 1, y);
    vertices.add(x, y + 1);
    vertices.add(x + 1, y + 1);
    edges_horiz.add(x, y);
    edges_horiz.add(x + 1, y);
    edges_vert.add(x, y);
    edges_vert.add(x, y + 1);
    rivers.add(x, y);
}
 
void init(int R, int C, int sr, int sc, int M, char *S) {
    add_river(sr, sc);
    mx_r = mn_r = sr;
    mx_c = mn_c = sc;
    FOR(i, 0, M) {
        if (S[i] == 'N') sr--;
        if (S[i] == 'E') sc++;
        if (S[i] == 'S') sr++;
        if (S[i] == 'W') sc--;
        add_river(sr, sc);
        mx_r = max(mx_r, sr);
        mn_r = min(mn_r, sr);
        mx_c = max(mx_c, sc);
        mn_c = min(mn_c, sc);
    }
    vertices.build();
    edges_horiz.build();
    edges_vert.build();
    rivers.build();
}
 
int colour(int ar, int ac, int br, int bc) {
    int E = edges_horiz.query(ar + 1, br, ac, bc) + edges_vert.query(ar, br, ac + 1, bc);
    int V = vertices.query(ar + 1, br, ac + 1, bc);
    int R = rivers.query(ar, br, ac, bc);
    int C = (ar >= mn_r || br <= mx_r || ac >= mn_c || bc <= mx_c ? 1 : 2);
    return E - V + C - R;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 41336 KB Output is correct
2 Correct 49 ms 42360 KB Output is correct
3 Correct 46 ms 41336 KB Output is correct
4 Correct 50 ms 41464 KB Output is correct
5 Correct 50 ms 42616 KB Output is correct
6 Correct 44 ms 41080 KB Output is correct
7 Correct 52 ms 41080 KB Output is correct
8 Correct 45 ms 41064 KB Output is correct
9 Correct 45 ms 41032 KB Output is correct
10 Correct 51 ms 41080 KB Output is correct
11 Correct 57 ms 41592 KB Output is correct
12 Correct 49 ms 41976 KB Output is correct
13 Correct 50 ms 43132 KB Output is correct
14 Correct 63 ms 43640 KB Output is correct
15 Correct 44 ms 41080 KB Output is correct
16 Correct 44 ms 41140 KB Output is correct
17 Correct 44 ms 41080 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 41140 KB Output is correct
2 Correct 44 ms 41080 KB Output is correct
3 Correct 818 ms 138256 KB Output is correct
4 Correct 1051 ms 202856 KB Output is correct
5 Correct 1049 ms 201492 KB Output is correct
6 Correct 870 ms 165140 KB Output is correct
7 Correct 982 ms 162936 KB Output is correct
8 Correct 367 ms 43432 KB Output is correct
9 Correct 1051 ms 203352 KB Output is correct
10 Correct 1057 ms 202008 KB Output is correct
11 Correct 1053 ms 165624 KB Output is correct
12 Correct 588 ms 192016 KB Output is correct
13 Correct 554 ms 203128 KB Output is correct
14 Correct 582 ms 201808 KB Output is correct
15 Correct 513 ms 165608 KB Output is correct
16 Correct 826 ms 156296 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 41080 KB Output is correct
2 Correct 535 ms 201168 KB Output is correct
3 Correct 272 ms 198664 KB Output is correct
4 Correct 295 ms 201248 KB Output is correct
5 Correct 284 ms 159992 KB Output is correct
6 Correct 141 ms 71288 KB Output is correct
7 Correct 240 ms 101112 KB Output is correct
8 Correct 419 ms 183876 KB Output is correct
9 Correct 434 ms 167864 KB Output is correct
10 Correct 154 ms 72824 KB Output is correct
11 Correct 276 ms 119516 KB Output is correct
12 Correct 532 ms 201072 KB Output is correct
13 Correct 271 ms 198552 KB Output is correct
14 Correct 312 ms 201224 KB Output is correct
15 Correct 286 ms 159864 KB Output is correct
16 Correct 133 ms 65144 KB Output is correct
17 Correct 224 ms 100984 KB Output is correct
18 Correct 412 ms 201168 KB Output is correct
19 Correct 421 ms 202232 KB Output is correct
20 Correct 407 ms 202140 KB Output is correct
21 Correct 413 ms 183864 KB Output is correct
22 Correct 395 ms 167800 KB Output is correct
23 Correct 153 ms 72824 KB Output is correct
24 Correct 279 ms 119572 KB Output is correct
25 Correct 538 ms 201060 KB Output is correct
26 Correct 273 ms 198648 KB Output is correct
27 Correct 310 ms 201080 KB Output is correct
28 Correct 279 ms 159864 KB Output is correct
29 Correct 130 ms 65144 KB Output is correct
30 Correct 225 ms 100984 KB Output is correct
31 Correct 411 ms 201236 KB Output is correct
32 Correct 470 ms 202268 KB Output is correct
33 Correct 408 ms 202020 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 41336 KB Output is correct
2 Correct 49 ms 42360 KB Output is correct
3 Correct 46 ms 41336 KB Output is correct
4 Correct 50 ms 41464 KB Output is correct
5 Correct 50 ms 42616 KB Output is correct
6 Correct 44 ms 41080 KB Output is correct
7 Correct 52 ms 41080 KB Output is correct
8 Correct 45 ms 41064 KB Output is correct
9 Correct 45 ms 41032 KB Output is correct
10 Correct 51 ms 41080 KB Output is correct
11 Correct 57 ms 41592 KB Output is correct
12 Correct 49 ms 41976 KB Output is correct
13 Correct 50 ms 43132 KB Output is correct
14 Correct 63 ms 43640 KB Output is correct
15 Correct 44 ms 41080 KB Output is correct
16 Correct 44 ms 41140 KB Output is correct
17 Correct 44 ms 41080 KB Output is correct
18 Correct 988 ms 124804 KB Output is correct
19 Correct 335 ms 48300 KB Output is correct
20 Correct 251 ms 45220 KB Output is correct
21 Correct 292 ms 45728 KB Output is correct
22 Correct 297 ms 46528 KB Output is correct
23 Correct 324 ms 48060 KB Output is correct
24 Correct 256 ms 45688 KB Output is correct
25 Correct 281 ms 46260 KB Output is correct
26 Correct 292 ms 46840 KB Output is correct
27 Correct 575 ms 109944 KB Output is correct
28 Correct 433 ms 75952 KB Output is correct
29 Correct 610 ms 104440 KB Output is correct
30 Correct 864 ms 204664 KB Output is correct
31 Correct 49 ms 41208 KB Output is correct
32 Correct 799 ms 110780 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 41336 KB Output is correct
2 Correct 49 ms 42360 KB Output is correct
3 Correct 46 ms 41336 KB Output is correct
4 Correct 50 ms 41464 KB Output is correct
5 Correct 50 ms 42616 KB Output is correct
6 Correct 44 ms 41080 KB Output is correct
7 Correct 52 ms 41080 KB Output is correct
8 Correct 45 ms 41064 KB Output is correct
9 Correct 45 ms 41032 KB Output is correct
10 Correct 51 ms 41080 KB Output is correct
11 Correct 57 ms 41592 KB Output is correct
12 Correct 49 ms 41976 KB Output is correct
13 Correct 50 ms 43132 KB Output is correct
14 Correct 63 ms 43640 KB Output is correct
15 Correct 44 ms 41080 KB Output is correct
16 Correct 44 ms 41140 KB Output is correct
17 Correct 44 ms 41080 KB Output is correct
18 Correct 988 ms 124804 KB Output is correct
19 Correct 335 ms 48300 KB Output is correct
20 Correct 251 ms 45220 KB Output is correct
21 Correct 292 ms 45728 KB Output is correct
22 Correct 297 ms 46528 KB Output is correct
23 Correct 324 ms 48060 KB Output is correct
24 Correct 256 ms 45688 KB Output is correct
25 Correct 281 ms 46260 KB Output is correct
26 Correct 292 ms 46840 KB Output is correct
27 Correct 575 ms 109944 KB Output is correct
28 Correct 433 ms 75952 KB Output is correct
29 Correct 610 ms 104440 KB Output is correct
30 Correct 864 ms 204664 KB Output is correct
31 Correct 49 ms 41208 KB Output is correct
32 Correct 799 ms 110780 KB Output is correct
33 Correct 535 ms 201168 KB Output is correct
34 Correct 272 ms 198664 KB Output is correct
35 Correct 295 ms 201248 KB Output is correct
36 Correct 284 ms 159992 KB Output is correct
37 Correct 141 ms 71288 KB Output is correct
38 Correct 240 ms 101112 KB Output is correct
39 Correct 419 ms 183876 KB Output is correct
40 Correct 434 ms 167864 KB Output is correct
41 Correct 154 ms 72824 KB Output is correct
42 Correct 276 ms 119516 KB Output is correct
43 Correct 532 ms 201072 KB Output is correct
44 Correct 271 ms 198552 KB Output is correct
45 Correct 312 ms 201224 KB Output is correct
46 Correct 286 ms 159864 KB Output is correct
47 Correct 133 ms 65144 KB Output is correct
48 Correct 224 ms 100984 KB Output is correct
49 Correct 412 ms 201168 KB Output is correct
50 Correct 421 ms 202232 KB Output is correct
51 Correct 407 ms 202140 KB Output is correct
52 Correct 413 ms 183864 KB Output is correct
53 Correct 395 ms 167800 KB Output is correct
54 Correct 153 ms 72824 KB Output is correct
55 Correct 279 ms 119572 KB Output is correct
56 Correct 538 ms 201060 KB Output is correct
57 Correct 273 ms 198648 KB Output is correct
58 Correct 310 ms 201080 KB Output is correct
59 Correct 279 ms 159864 KB Output is correct
60 Correct 130 ms 65144 KB Output is correct
61 Correct 225 ms 100984 KB Output is correct
62 Correct 411 ms 201236 KB Output is correct
63 Correct 470 ms 202268 KB Output is correct
64 Correct 408 ms 202020 KB Output is correct
65 Correct 1361 ms 187412 KB Output is correct
66 Correct 1380 ms 171484 KB Output is correct
67 Correct 760 ms 76456 KB Output is correct
68 Correct 903 ms 123204 KB Output is correct
69 Correct 1135 ms 204860 KB Output is correct
70 Correct 792 ms 202244 KB Output is correct
71 Correct 784 ms 204744 KB Output is correct
72 Correct 751 ms 163576 KB Output is correct
73 Correct 517 ms 68740 KB Output is correct
74 Correct 591 ms 104780 KB Output is correct
75 Correct 774 ms 204820 KB Output is correct
76 Correct 954 ms 205748 KB Output is correct
77 Correct 810 ms 205560 KB Output is correct
78 Correct 818 ms 138256 KB Output is correct
79 Correct 1051 ms 202856 KB Output is correct
80 Correct 1049 ms 201492 KB Output is correct
81 Correct 870 ms 165140 KB Output is correct
82 Correct 982 ms 162936 KB Output is correct
83 Correct 367 ms 43432 KB Output is correct
84 Correct 1051 ms 203352 KB Output is correct
85 Correct 1057 ms 202008 KB Output is correct
86 Correct 1053 ms 165624 KB Output is correct
87 Correct 588 ms 192016 KB Output is correct
88 Correct 554 ms 203128 KB Output is correct
89 Correct 582 ms 201808 KB Output is correct
90 Correct 513 ms 165608 KB Output is correct
91 Correct 826 ms 156296 KB Output is correct