oj.uz

Submission #158876

# Submission time Handle Problem Language Result Execution time Memory
158876 2019-10-19T09:12:05 Z PeppaPig Land of the Rainbow Gold (APIO17_rainbow) C++14
100 / 100
 1281 ms 80812 KB 
#include "rainbow.h"
#include <bits/stdc++.h>

#define pii pair<int, int>
#define x first
#define y second

using namespace std;

const int N = 2e5+5;

struct FenwickSet {
    vector<pii> add; 
    vector<int> v[N];
    
    void update(int x, int k) {
        for(int i = x; i < N; i += i & -i) v[i].emplace_back(k);
    }

    int query(int x, int l, int r) {
        int ret = 0;
        for(int i = x; i; i -= i & -i) {
            auto L = lower_bound(v[i].begin(), v[i].end(), l);
            auto R = upper_bound(v[i].begin(), v[i].end(), r);
            ret += R - L;
        }
        return ret;
    }

    void init() {
        sort(add.begin(), add.end());
        add.resize(unique(add.begin(), add.end()) - add.begin());
        for(pii p : add) update(p.x, p.y);
        for(int i = 1; i < N; i++) sort(v[i].begin(), v[i].end());
    }

    int count(int x1, int x2, int y1, int y2) {
        if(x1 > x2 || y1 > y2) return 0;
        return query(x2, y1, y2) - query(x1 - 1, y1, y2);
    }
} t[4];

// t[0] = River cells
// t[1] = River vertices
// t[2] = Vertical edges
// t[3] = Horizontal edges

int min_r, min_c, max_r, max_c;

void add_river(pii p) {
    min_r = min(min_r, p.x), max_r = max(max_r, p.x);
    min_c = min(min_c, p.y), max_c = max(max_c, p.y);
    t[0].add.emplace_back(p);
    for(int i = 0; i < 2; i++) for(int j = 0; j < 2; j++)
        t[1].add.emplace_back(p.x + i, p.y + j);
    for(int i = 0; i < 2; i++) {
        t[2].add.emplace_back(p.x, p.y + i);
        t[3].add.emplace_back(p.x + i, p.y);
    }
}

//f = 1 - v + e
int solve(int x1, int x2, int y1, int y2) {
    int v = t[1].count(x1+1, x2, y1+1, y2); // + 4 sides vertices with no corner + 4 corners
    int e = t[2].count(x1, x2, y1+1, y2) + t[3].count(x1+1, x2, y1, y2); // + 4 sides vertices + 4(+1 each side for edge)
    int river = t[0].count(x1, x2, y1, y2);
    return 1 - v + e - river; //4 sides and corners cancel each other
}

void init(int R, int C, int sr, int sc, int M, char *S) {
    min_r = min_c = 1e9, max_r = max_c = -1e9;
    pii now(sr, sc);
    add_river(now);
    for(int i = 0; i < M; i++) {
        if(S[i] == 'N') --now.x;
        if(S[i] == 'S') ++now.x;
        if(S[i] == 'E') ++now.y;
        if(S[i] == 'W') --now.y;
        add_river(now);
    }
    for(int i = 0; i < 4; i++) t[i].init();
}

int colour(int ar, int ac, int br, int bc) {
    if(ar < min_r && max_r < br && ac < min_c && max_c < bc)
        return solve(min_r - 1, max_r + 1, min_c - 1, max_c + 1) + 1;
    else return solve(ar, br, ac, bc);
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 19192 KB Output is correct
2 Correct 28 ms 19576 KB Output is correct
3 Correct 22 ms 19320 KB Output is correct
4 Correct 23 ms 19320 KB Output is correct
5 Correct 29 ms 19832 KB Output is correct
6 Correct 20 ms 19064 KB Output is correct
7 Correct 20 ms 19064 KB Output is correct
8 Correct 21 ms 19192 KB Output is correct
9 Correct 20 ms 19192 KB Output is correct
10 Correct 20 ms 19064 KB Output is correct
11 Correct 24 ms 19448 KB Output is correct
12 Correct 26 ms 19576 KB Output is correct
13 Correct 29 ms 19832 KB Output is correct
14 Correct 33 ms 20216 KB Output is correct
15 Correct 20 ms 19192 KB Output is correct
16 Correct 20 ms 19064 KB Output is correct
17 Correct 20 ms 19064 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 19064 KB Output is correct
2 Correct 20 ms 19064 KB Output is correct
3 Correct 602 ms 53708 KB Output is correct
4 Correct 941 ms 80604 KB Output is correct
5 Correct 957 ms 80612 KB Output is correct
6 Correct 781 ms 75172 KB Output is correct
7 Correct 760 ms 70364 KB Output is correct
8 Correct 139 ms 31580 KB Output is correct
9 Correct 862 ms 80812 KB Output is correct
10 Correct 914 ms 80604 KB Output is correct
11 Correct 775 ms 75104 KB Output is correct
12 Correct 931 ms 78236 KB Output is correct
13 Correct 800 ms 80604 KB Output is correct
14 Correct 786 ms 80732 KB Output is correct
15 Correct 696 ms 75200 KB Output is correct
16 Correct 733 ms 72088 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 19192 KB Output is correct
2 Correct 459 ms 53356 KB Output is correct
3 Correct 225 ms 57564 KB Output is correct
4 Correct 229 ms 57792 KB Output is correct
5 Correct 251 ms 48328 KB Output is correct
6 Correct 154 ms 32476 KB Output is correct
7 Correct 191 ms 35164 KB Output is correct
8 Correct 596 ms 72284 KB Output is correct
9 Correct 565 ms 68828 KB Output is correct
10 Correct 133 ms 28900 KB Output is correct
11 Correct 248 ms 41920 KB Output is correct
12 Correct 453 ms 53408 KB Output is correct
13 Correct 219 ms 57436 KB Output is correct
14 Correct 229 ms 57724 KB Output is correct
15 Correct 244 ms 48376 KB Output is correct
16 Correct 153 ms 31452 KB Output is correct
17 Correct 223 ms 39132 KB Output is correct
18 Correct 492 ms 67412 KB Output is correct
19 Correct 335 ms 56796 KB Output is correct
20 Correct 392 ms 60636 KB Output is correct
21 Correct 598 ms 72216 KB Output is correct
22 Correct 555 ms 68956 KB Output is correct
23 Correct 126 ms 28900 KB Output is correct
24 Correct 250 ms 41968 KB Output is correct
25 Correct 454 ms 53340 KB Output is correct
26 Correct 220 ms 57436 KB Output is correct
27 Correct 229 ms 57704 KB Output is correct
28 Correct 245 ms 48444 KB Output is correct
29 Correct 153 ms 31452 KB Output is correct
30 Correct 224 ms 39100 KB Output is correct
31 Correct 494 ms 67292 KB Output is correct
32 Correct 337 ms 56796 KB Output is correct
33 Correct 393 ms 60640 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 19192 KB Output is correct
2 Correct 28 ms 19576 KB Output is correct
3 Correct 22 ms 19320 KB Output is correct
4 Correct 23 ms 19320 KB Output is correct
5 Correct 29 ms 19832 KB Output is correct
6 Correct 20 ms 19064 KB Output is correct
7 Correct 20 ms 19064 KB Output is correct
8 Correct 21 ms 19192 KB Output is correct
9 Correct 20 ms 19192 KB Output is correct
10 Correct 20 ms 19064 KB Output is correct
11 Correct 24 ms 19448 KB Output is correct
12 Correct 26 ms 19576 KB Output is correct
13 Correct 29 ms 19832 KB Output is correct
14 Correct 33 ms 20216 KB Output is correct
15 Correct 20 ms 19192 KB Output is correct
16 Correct 20 ms 19064 KB Output is correct
17 Correct 20 ms 19064 KB Output is correct
18 Correct 1281 ms 49020 KB Output is correct
19 Correct 333 ms 24184 KB Output is correct
20 Correct 255 ms 22824 KB Output is correct
21 Correct 292 ms 23032 KB Output is correct
22 Correct 316 ms 23268 KB Output is correct
23 Correct 316 ms 24056 KB Output is correct
24 Correct 303 ms 23260 KB Output is correct
25 Correct 344 ms 23416 KB Output is correct
26 Correct 338 ms 23772 KB Output is correct
27 Correct 566 ms 45456 KB Output is correct
28 Correct 474 ms 37540 KB Output is correct
29 Correct 515 ms 43108 KB Output is correct
30 Correct 1089 ms 70872 KB Output is correct
31 Correct 24 ms 19192 KB Output is correct
32 Correct 913 ms 48016 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 19192 KB Output is correct
2 Correct 28 ms 19576 KB Output is correct
3 Correct 22 ms 19320 KB Output is correct
4 Correct 23 ms 19320 KB Output is correct
5 Correct 29 ms 19832 KB Output is correct
6 Correct 20 ms 19064 KB Output is correct
7 Correct 20 ms 19064 KB Output is correct
8 Correct 21 ms 19192 KB Output is correct
9 Correct 20 ms 19192 KB Output is correct
10 Correct 20 ms 19064 KB Output is correct
11 Correct 24 ms 19448 KB Output is correct
12 Correct 26 ms 19576 KB Output is correct
13 Correct 29 ms 19832 KB Output is correct
14 Correct 33 ms 20216 KB Output is correct
15 Correct 20 ms 19192 KB Output is correct
16 Correct 20 ms 19064 KB Output is correct
17 Correct 20 ms 19064 KB Output is correct
18 Correct 1281 ms 49020 KB Output is correct
19 Correct 333 ms 24184 KB Output is correct
20 Correct 255 ms 22824 KB Output is correct
21 Correct 292 ms 23032 KB Output is correct
22 Correct 316 ms 23268 KB Output is correct
23 Correct 316 ms 24056 KB Output is correct
24 Correct 303 ms 23260 KB Output is correct
25 Correct 344 ms 23416 KB Output is correct
26 Correct 338 ms 23772 KB Output is correct
27 Correct 566 ms 45456 KB Output is correct
28 Correct 474 ms 37540 KB Output is correct
29 Correct 515 ms 43108 KB Output is correct
30 Correct 1089 ms 70872 KB Output is correct
31 Correct 24 ms 19192 KB Output is correct
32 Correct 913 ms 48016 KB Output is correct
33 Correct 459 ms 53356 KB Output is correct
34 Correct 225 ms 57564 KB Output is correct
35 Correct 229 ms 57792 KB Output is correct
36 Correct 251 ms 48328 KB Output is correct
37 Correct 154 ms 32476 KB Output is correct
38 Correct 191 ms 35164 KB Output is correct
39 Correct 596 ms 72284 KB Output is correct
40 Correct 565 ms 68828 KB Output is correct
41 Correct 133 ms 28900 KB Output is correct
42 Correct 248 ms 41920 KB Output is correct
43 Correct 453 ms 53408 KB Output is correct
44 Correct 219 ms 57436 KB Output is correct
45 Correct 229 ms 57724 KB Output is correct
46 Correct 244 ms 48376 KB Output is correct
47 Correct 153 ms 31452 KB Output is correct
48 Correct 223 ms 39132 KB Output is correct
49 Correct 492 ms 67412 KB Output is correct
50 Correct 335 ms 56796 KB Output is correct
51 Correct 392 ms 60636 KB Output is correct
52 Correct 598 ms 72216 KB Output is correct
53 Correct 555 ms 68956 KB Output is correct
54 Correct 126 ms 28900 KB Output is correct
55 Correct 250 ms 41968 KB Output is correct
56 Correct 454 ms 53340 KB Output is correct
57 Correct 220 ms 57436 KB Output is correct
58 Correct 229 ms 57704 KB Output is correct
59 Correct 245 ms 48444 KB Output is correct
60 Correct 153 ms 31452 KB Output is correct
61 Correct 224 ms 39100 KB Output is correct
62 Correct 494 ms 67292 KB Output is correct
63 Correct 337 ms 56796 KB Output is correct
64 Correct 393 ms 60640 KB Output is correct
65 Correct 1022 ms 75724 KB Output is correct
66 Correct 1041 ms 72280 KB Output is correct
67 Correct 466 ms 32484 KB Output is correct
68 Correct 636 ms 45528 KB Output is correct
69 Correct 768 ms 56796 KB Output is correct
70 Correct 751 ms 61012 KB Output is correct
71 Correct 617 ms 61372 KB Output is correct
72 Correct 623 ms 52032 KB Output is correct
73 Correct 386 ms 35028 KB Output is correct
74 Correct 456 ms 42712 KB Output is correct
75 Correct 762 ms 71004 KB Output is correct
76 Correct 810 ms 60500 KB Output is correct
77 Correct 699 ms 64220 KB Output is correct
78 Correct 602 ms 53708 KB Output is correct
79 Correct 941 ms 80604 KB Output is correct
80 Correct 957 ms 80612 KB Output is correct
81 Correct 781 ms 75172 KB Output is correct
82 Correct 760 ms 70364 KB Output is correct
83 Correct 139 ms 31580 KB Output is correct
84 Correct 862 ms 80812 KB Output is correct
85 Correct 914 ms 80604 KB Output is correct
86 Correct 775 ms 75104 KB Output is correct
87 Correct 931 ms 78236 KB Output is correct
88 Correct 800 ms 80604 KB Output is correct
89 Correct 786 ms 80732 KB Output is correct
90 Correct 696 ms 75200 KB Output is correct
91 Correct 733 ms 72088 KB Output is correct