oj.uz

Submission #202247

# Submission time Handle Problem Language Result Execution time Memory
202247 2020-02-14T14:21:19 Z stefanbalaz2 Land of the Rainbow Gold (APIO17_rainbow) C++14
100 / 100
 1353 ms 205688 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
- Since the river is a big connected component, we can just check if the river touches the bounding
  rectangle to determine the number of components
- The formula also counts the big background face so we must subtract that from the answer
- To answer 2d range queries online, we can use a 2d segment tree
    - Or in this case, since there are no updates, a persistent segment tree
*/
 
#include "rainbow.h"
#include <bits/stdc++.h>
#pragma GCC Optimize("unroll-loops")
#pragma GCC Optimize("O3")
#pragma GCC target("sse4,avx2,fma,avx")
#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;
}

Compilation message

rainbow.cpp:21:0: warning: ignoring #pragma GCC Optimize [-Wunknown-pragmas]
 #pragma GCC Optimize("unroll-loops")
 
rainbow.cpp:22:0: warning: ignoring #pragma GCC Optimize [-Wunknown-pragmas]
 #pragma GCC Optimize("O3")

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 41336 KB Output is correct
2 Correct 36 ms 42360 KB Output is correct
3 Correct 33 ms 41340 KB Output is correct
4 Correct 34 ms 41460 KB Output is correct
5 Correct 35 ms 42616 KB Output is correct
6 Correct 32 ms 41080 KB Output is correct
7 Correct 33 ms 41208 KB Output is correct
8 Correct 34 ms 41080 KB Output is correct
9 Correct 31 ms 41080 KB Output is correct
10 Correct 33 ms 41084 KB Output is correct
11 Correct 35 ms 41592 KB Output is correct
12 Correct 35 ms 41976 KB Output is correct
13 Correct 38 ms 43128 KB Output is correct
14 Correct 38 ms 43640 KB Output is correct
15 Correct 31 ms 41080 KB Output is correct
16 Correct 32 ms 41080 KB Output is correct
17 Correct 32 ms 41080 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 41080 KB Output is correct
2 Correct 32 ms 41080 KB Output is correct
3 Correct 695 ms 139640 KB Output is correct
4 Correct 957 ms 204272 KB Output is correct
5 Correct 993 ms 202824 KB Output is correct
6 Correct 806 ms 166444 KB Output is correct
7 Correct 900 ms 164372 KB Output is correct
8 Correct 358 ms 44280 KB Output is correct
9 Correct 968 ms 204188 KB Output is correct
10 Correct 970 ms 202772 KB Output is correct
11 Correct 863 ms 166392 KB Output is correct
12 Correct 458 ms 192888 KB Output is correct
13 Correct 482 ms 204280 KB Output is correct
14 Correct 479 ms 202872 KB Output is correct
15 Correct 469 ms 166628 KB Output is correct
16 Correct 752 ms 157176 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 41080 KB Output is correct
2 Correct 405 ms 201280 KB Output is correct
3 Correct 202 ms 198520 KB Output is correct
4 Correct 220 ms 201136 KB Output is correct
5 Correct 206 ms 159864 KB Output is correct
6 Correct 117 ms 71160 KB Output is correct
7 Correct 185 ms 100856 KB Output is correct
8 Correct 333 ms 183800 KB Output is correct
9 Correct 330 ms 167800 KB Output is correct
10 Correct 119 ms 72696 KB Output is correct
11 Correct 201 ms 119544 KB Output is correct
12 Correct 388 ms 201112 KB Output is correct
13 Correct 198 ms 198640 KB Output is correct
14 Correct 211 ms 201080 KB Output is correct
15 Correct 198 ms 159864 KB Output is correct
16 Correct 114 ms 65144 KB Output is correct
17 Correct 177 ms 101008 KB Output is correct
18 Correct 295 ms 201080 KB Output is correct
19 Correct 288 ms 202212 KB Output is correct
20 Correct 285 ms 202104 KB Output is correct
21 Correct 344 ms 183928 KB Output is correct
22 Correct 314 ms 167932 KB Output is correct
23 Correct 121 ms 72696 KB Output is correct
24 Correct 205 ms 119532 KB Output is correct
25 Correct 383 ms 201208 KB Output is correct
26 Correct 201 ms 198524 KB Output is correct
27 Correct 213 ms 201080 KB Output is correct
28 Correct 195 ms 159864 KB Output is correct
29 Correct 135 ms 65144 KB Output is correct
30 Correct 170 ms 100984 KB Output is correct
31 Correct 304 ms 201212 KB Output is correct
32 Correct 310 ms 202224 KB Output is correct
33 Correct 288 ms 201976 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 41336 KB Output is correct
2 Correct 36 ms 42360 KB Output is correct
3 Correct 33 ms 41340 KB Output is correct
4 Correct 34 ms 41460 KB Output is correct
5 Correct 35 ms 42616 KB Output is correct
6 Correct 32 ms 41080 KB Output is correct
7 Correct 33 ms 41208 KB Output is correct
8 Correct 34 ms 41080 KB Output is correct
9 Correct 31 ms 41080 KB Output is correct
10 Correct 33 ms 41084 KB Output is correct
11 Correct 35 ms 41592 KB Output is correct
12 Correct 35 ms 41976 KB Output is correct
13 Correct 38 ms 43128 KB Output is correct
14 Correct 38 ms 43640 KB Output is correct
15 Correct 31 ms 41080 KB Output is correct
16 Correct 32 ms 41080 KB Output is correct
17 Correct 32 ms 41080 KB Output is correct
18 Correct 971 ms 125456 KB Output is correct
19 Correct 297 ms 48112 KB Output is correct
20 Correct 228 ms 45048 KB Output is correct
21 Correct 246 ms 45816 KB Output is correct
22 Correct 268 ms 46456 KB Output is correct
23 Correct 297 ms 47864 KB Output is correct
24 Correct 230 ms 45560 KB Output is correct
25 Correct 253 ms 46456 KB Output is correct
26 Correct 262 ms 46840 KB Output is correct
27 Correct 490 ms 109688 KB Output is correct
28 Correct 418 ms 75896 KB Output is correct
29 Correct 524 ms 104056 KB Output is correct
30 Correct 780 ms 204700 KB Output is correct
31 Correct 38 ms 41208 KB Output is correct
32 Correct 767 ms 110456 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 41336 KB Output is correct
2 Correct 36 ms 42360 KB Output is correct
3 Correct 33 ms 41340 KB Output is correct
4 Correct 34 ms 41460 KB Output is correct
5 Correct 35 ms 42616 KB Output is correct
6 Correct 32 ms 41080 KB Output is correct
7 Correct 33 ms 41208 KB Output is correct
8 Correct 34 ms 41080 KB Output is correct
9 Correct 31 ms 41080 KB Output is correct
10 Correct 33 ms 41084 KB Output is correct
11 Correct 35 ms 41592 KB Output is correct
12 Correct 35 ms 41976 KB Output is correct
13 Correct 38 ms 43128 KB Output is correct
14 Correct 38 ms 43640 KB Output is correct
15 Correct 31 ms 41080 KB Output is correct
16 Correct 32 ms 41080 KB Output is correct
17 Correct 32 ms 41080 KB Output is correct
18 Correct 971 ms 125456 KB Output is correct
19 Correct 297 ms 48112 KB Output is correct
20 Correct 228 ms 45048 KB Output is correct
21 Correct 246 ms 45816 KB Output is correct
22 Correct 268 ms 46456 KB Output is correct
23 Correct 297 ms 47864 KB Output is correct
24 Correct 230 ms 45560 KB Output is correct
25 Correct 253 ms 46456 KB Output is correct
26 Correct 262 ms 46840 KB Output is correct
27 Correct 490 ms 109688 KB Output is correct
28 Correct 418 ms 75896 KB Output is correct
29 Correct 524 ms 104056 KB Output is correct
30 Correct 780 ms 204700 KB Output is correct
31 Correct 38 ms 41208 KB Output is correct
32 Correct 767 ms 110456 KB Output is correct
33 Correct 405 ms 201280 KB Output is correct
34 Correct 202 ms 198520 KB Output is correct
35 Correct 220 ms 201136 KB Output is correct
36 Correct 206 ms 159864 KB Output is correct
37 Correct 117 ms 71160 KB Output is correct
38 Correct 185 ms 100856 KB Output is correct
39 Correct 333 ms 183800 KB Output is correct
40 Correct 330 ms 167800 KB Output is correct
41 Correct 119 ms 72696 KB Output is correct
42 Correct 201 ms 119544 KB Output is correct
43 Correct 388 ms 201112 KB Output is correct
44 Correct 198 ms 198640 KB Output is correct
45 Correct 211 ms 201080 KB Output is correct
46 Correct 198 ms 159864 KB Output is correct
47 Correct 114 ms 65144 KB Output is correct
48 Correct 177 ms 101008 KB Output is correct
49 Correct 295 ms 201080 KB Output is correct
50 Correct 288 ms 202212 KB Output is correct
51 Correct 285 ms 202104 KB Output is correct
52 Correct 344 ms 183928 KB Output is correct
53 Correct 314 ms 167932 KB Output is correct
54 Correct 121 ms 72696 KB Output is correct
55 Correct 205 ms 119532 KB Output is correct
56 Correct 383 ms 201208 KB Output is correct
57 Correct 201 ms 198524 KB Output is correct
58 Correct 213 ms 201080 KB Output is correct
59 Correct 195 ms 159864 KB Output is correct
60 Correct 135 ms 65144 KB Output is correct
61 Correct 170 ms 100984 KB Output is correct
62 Correct 304 ms 201212 KB Output is correct
63 Correct 310 ms 202224 KB Output is correct
64 Correct 288 ms 201976 KB Output is correct
65 Correct 1353 ms 187128 KB Output is correct
66 Correct 1325 ms 171128 KB Output is correct
67 Correct 553 ms 76284 KB Output is correct
68 Correct 641 ms 123004 KB Output is correct
69 Correct 927 ms 204416 KB Output is correct
70 Correct 665 ms 201792 KB Output is correct
71 Correct 680 ms 204408 KB Output is correct
72 Correct 639 ms 163320 KB Output is correct
73 Correct 452 ms 68344 KB Output is correct
74 Correct 520 ms 104312 KB Output is correct
75 Correct 646 ms 204416 KB Output is correct
76 Correct 842 ms 205688 KB Output is correct
77 Correct 688 ms 205560 KB Output is correct
78 Correct 695 ms 139640 KB Output is correct
79 Correct 957 ms 204272 KB Output is correct
80 Correct 993 ms 202824 KB Output is correct
81 Correct 806 ms 166444 KB Output is correct
82 Correct 900 ms 164372 KB Output is correct
83 Correct 358 ms 44280 KB Output is correct
84 Correct 968 ms 204188 KB Output is correct
85 Correct 970 ms 202772 KB Output is correct
86 Correct 863 ms 166392 KB Output is correct
87 Correct 458 ms 192888 KB Output is correct
88 Correct 482 ms 204280 KB Output is correct
89 Correct 479 ms 202872 KB Output is correct
90 Correct 469 ms 166628 KB Output is correct
91 Correct 752 ms 157176 KB Output is correct