oj.uz

Submission #566722

# Submission time Handle Problem Language Result Execution time Memory
566722 2022-05-22T18:11:24 Z hoanghq2004 Land of the Rainbow Gold (APIO17_rainbow) C++14
100 / 100
 1603 ms 189304 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "rainbow.h"

using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

const int N = 2e5 + 10;

set <pair <int, int>> V, X, Y, s;
int maxx, minx, maxy, miny;


struct range_tree {
    vector <int> BIT[N], dta[N];
    vector <tuple <int, int, int>> work;
    void add(int x, int y, int val) {
        work.push_back({x, y, val});
        for (; x < N; x += x & - x)
            dta[x].push_back(y);
    }
    void build() {
        for (int i = 0; i < N; ++i) {
            sort(dta[i].begin(), dta[i].end());
            dta[i].erase(unique(dta[i].begin(), dta[i].end()), dta[i].end());
            BIT[i].assign(dta[i].size() + 10, 0);
        }
        for (auto [x, y, val]: work) {
            for (; x < N; x += x & - x) {
                int z = lower_bound(dta[x].begin(), dta[x].end(), y) - dta[x].begin() + 1;
                for (; z < BIT[x].size(); z += z & - z)
                    BIT[x][z] += val;
            }
        }
    }
    int get(int x, int y) {
        int ans = 0;
        for (; x; x -= x & - x) {
            int z = upper_bound(dta[x].begin(), dta[x].end(), y) - dta[x].begin();
            for (; z; z -= z & - z)
                ans += BIT[x][z];
        }
        return ans;
    }

    int get(int x, int y, int u, int v) {
        return get(u, v) - get(x - 1, v) - get(u, y - 1) + get(x - 1, y - 1);
    }
} cnt[4];


void init(int R, int C, int x, int y, int M, char *S) {
    s.insert({x, y});
    maxx = minx = x;
    ++maxx;
    maxy = miny = y;
    ++maxy;
    for (int i = 0; i < M; ++i) {
        if (S[i] == 'N') --x;
        if (S[i] == 'S') ++x;
        if (S[i] == 'E') ++y;
        if (S[i] == 'W') --y;
        maxx = max(maxx, x + 1);
        minx = min(minx, x);
        maxy = max(maxy, y + 1);
        miny = min(miny, y);
        s.insert({x, y});
    }
    for (auto [x, y]: s) {
        V.insert({x, y});
        V.insert({x, y + 1});
        V.insert({x + 1, y});
        V.insert({x + 1, y + 1});
        X.insert({x, y});
        Y.insert({x, y});
        X.insert({x, y + 1});
        Y.insert({x + 1, y});
    }
    for (auto [x, y]: s) cnt[0].add(x, y, 1);
    for (auto [x, y]: V) cnt[1].add(x, y, 1);
    for (auto [x, y]: X) cnt[2].add(x, y, 1);
    for (auto [x, y]: Y) cnt[3].add(x, y, 1);
    cnt[0].build();
    cnt[1].build();
    cnt[2].build();
    cnt[3].build();
}

int colour(int _x, int _y, int _u, int _v) {
    ++_u, ++_v;
    int v = cnt[1].get(_x + 1, _y + 1, _u - 1, _v - 1);
    int e = cnt[2].get(_x, _y + 1, _u - 1, _v - 1) + cnt[3].get(_x + 1, _y, _u - 1, _v - 1);
    int r = cnt[0].get(_x, _y, _u - 1, _v - 1);
    return e - v + 1 + (_x < minx && _u > maxx && _y < miny && _v > maxy) - r;
}
////
//static int R, C, M, Q;
//static int sr, sc;
//static char S[100000 + 5];
//
//int main() {
//    scanf("%d %d %d %d", &R, &C, &M, &Q);
//    scanf("%d %d", &sr, &sc);
//    if (M > 0) {
//        scanf(" %s ", S);
//    }
//
//    init(R, C, sr, sc, M, S);
//
//    int query;
//    for (query = 0; query < Q; query++) {
//        int ar, ac, br, bc;
//        scanf("%d %d %d %d", &ar, &ac, &br, &bc);
//        printf("%d\n", colour(ar, ac, br, bc));
//    }
//
//    return 0;
//}

Compilation message

rainbow.cpp: In member function 'void range_tree::build()':
rainbow.cpp:34:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   34 |         for (auto [x, y, val]: work) {
      |                   ^
rainbow.cpp:37:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |                 for (; z < BIT[x].size(); z += z & - z)
      |                        ~~^~~~~~~~~~~~~~~
rainbow.cpp: In function 'void init(int, int, int, int, int, char*)':
rainbow.cpp:75:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   75 |     for (auto [x, y]: s) {
      |               ^
rainbow.cpp:85:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   85 |     for (auto [x, y]: s) cnt[0].add(x, y, 1);
      |               ^
rainbow.cpp:86:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   86 |     for (auto [x, y]: V) cnt[1].add(x, y, 1);
      |               ^
rainbow.cpp:87:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   87 |     for (auto [x, y]: X) cnt[2].add(x, y, 1);
      |               ^
rainbow.cpp:88:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   88 |     for (auto [x, y]: Y) cnt[3].add(x, y, 1);
      |               ^

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 75656 KB Output is correct
2 Correct 77 ms 76204 KB Output is correct
3 Correct 65 ms 75556 KB Output is correct
4 Correct 68 ms 75640 KB Output is correct
5 Correct 77 ms 76400 KB Output is correct
6 Correct 59 ms 75356 KB Output is correct
7 Correct 58 ms 75372 KB Output is correct
8 Correct 58 ms 75340 KB Output is correct
9 Correct 68 ms 75360 KB Output is correct
10 Correct 62 ms 75340 KB Output is correct
11 Correct 63 ms 75792 KB Output is correct
12 Correct 72 ms 75992 KB Output is correct
13 Correct 84 ms 76624 KB Output is correct
14 Correct 86 ms 76880 KB Output is correct
15 Correct 63 ms 75340 KB Output is correct
16 Correct 60 ms 75388 KB Output is correct
17 Correct 60 ms 75336 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 75388 KB Output is correct
2 Correct 60 ms 75336 KB Output is correct
3 Correct 954 ms 142460 KB Output is correct
4 Correct 1603 ms 189304 KB Output is correct
5 Correct 1539 ms 186932 KB Output is correct
6 Correct 1240 ms 162064 KB Output is correct
7 Correct 1240 ms 156952 KB Output is correct
8 Correct 120 ms 79016 KB Output is correct
9 Correct 1510 ms 189216 KB Output is correct
10 Correct 1542 ms 186500 KB Output is correct
11 Correct 1255 ms 161940 KB Output is correct
12 Correct 1558 ms 182504 KB Output is correct
13 Correct 1405 ms 189172 KB Output is correct
14 Correct 1405 ms 186504 KB Output is correct
15 Correct 1178 ms 161928 KB Output is correct
16 Correct 1146 ms 163264 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 75340 KB Output is correct
2 Correct 790 ms 152748 KB Output is correct
3 Correct 460 ms 148112 KB Output is correct
4 Correct 745 ms 153460 KB Output is correct
5 Correct 444 ms 131984 KB Output is correct
6 Correct 183 ms 88168 KB Output is correct
7 Correct 293 ms 98220 KB Output is correct
8 Correct 1002 ms 163172 KB Output is correct
9 Correct 903 ms 154344 KB Output is correct
10 Correct 187 ms 89404 KB Output is correct
11 Correct 434 ms 110956 KB Output is correct
12 Correct 806 ms 152752 KB Output is correct
13 Correct 435 ms 148080 KB Output is correct
14 Correct 717 ms 153464 KB Output is correct
15 Correct 447 ms 132044 KB Output is correct
16 Correct 176 ms 85788 KB Output is correct
17 Correct 314 ms 101584 KB Output is correct
18 Correct 756 ms 154400 KB Output is correct
19 Correct 658 ms 151840 KB Output is correct
20 Correct 755 ms 157944 KB Output is correct
21 Correct 989 ms 163144 KB Output is correct
22 Correct 895 ms 154348 KB Output is correct
23 Correct 210 ms 89512 KB Output is correct
24 Correct 387 ms 110968 KB Output is correct
25 Correct 819 ms 152724 KB Output is correct
26 Correct 458 ms 148140 KB Output is correct
27 Correct 719 ms 153464 KB Output is correct
28 Correct 443 ms 131912 KB Output is correct
29 Correct 178 ms 85804 KB Output is correct
30 Correct 316 ms 101568 KB Output is correct
31 Correct 762 ms 154488 KB Output is correct
32 Correct 668 ms 151856 KB Output is correct
33 Correct 732 ms 157968 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 75656 KB Output is correct
2 Correct 77 ms 76204 KB Output is correct
3 Correct 65 ms 75556 KB Output is correct
4 Correct 68 ms 75640 KB Output is correct
5 Correct 77 ms 76400 KB Output is correct
6 Correct 59 ms 75356 KB Output is correct
7 Correct 58 ms 75372 KB Output is correct
8 Correct 58 ms 75340 KB Output is correct
9 Correct 68 ms 75360 KB Output is correct
10 Correct 62 ms 75340 KB Output is correct
11 Correct 63 ms 75792 KB Output is correct
12 Correct 72 ms 75992 KB Output is correct
13 Correct 84 ms 76624 KB Output is correct
14 Correct 86 ms 76880 KB Output is correct
15 Correct 63 ms 75340 KB Output is correct
16 Correct 60 ms 75388 KB Output is correct
17 Correct 60 ms 75336 KB Output is correct
18 Correct 952 ms 117056 KB Output is correct
19 Correct 344 ms 81276 KB Output is correct
20 Correct 239 ms 79188 KB Output is correct
21 Correct 273 ms 79796 KB Output is correct
22 Correct 291 ms 80056 KB Output is correct
23 Correct 334 ms 81156 KB Output is correct
24 Correct 304 ms 79600 KB Output is correct
25 Correct 316 ms 80068 KB Output is correct
26 Correct 327 ms 80220 KB Output is correct
27 Correct 552 ms 109208 KB Output is correct
28 Correct 416 ms 93592 KB Output is correct
29 Correct 518 ms 105712 KB Output is correct
30 Correct 1046 ms 157980 KB Output is correct
31 Correct 67 ms 75532 KB Output is correct
32 Correct 679 ms 112544 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 75656 KB Output is correct
2 Correct 77 ms 76204 KB Output is correct
3 Correct 65 ms 75556 KB Output is correct
4 Correct 68 ms 75640 KB Output is correct
5 Correct 77 ms 76400 KB Output is correct
6 Correct 59 ms 75356 KB Output is correct
7 Correct 58 ms 75372 KB Output is correct
8 Correct 58 ms 75340 KB Output is correct
9 Correct 68 ms 75360 KB Output is correct
10 Correct 62 ms 75340 KB Output is correct
11 Correct 63 ms 75792 KB Output is correct
12 Correct 72 ms 75992 KB Output is correct
13 Correct 84 ms 76624 KB Output is correct
14 Correct 86 ms 76880 KB Output is correct
15 Correct 63 ms 75340 KB Output is correct
16 Correct 60 ms 75388 KB Output is correct
17 Correct 60 ms 75336 KB Output is correct
18 Correct 952 ms 117056 KB Output is correct
19 Correct 344 ms 81276 KB Output is correct
20 Correct 239 ms 79188 KB Output is correct
21 Correct 273 ms 79796 KB Output is correct
22 Correct 291 ms 80056 KB Output is correct
23 Correct 334 ms 81156 KB Output is correct
24 Correct 304 ms 79600 KB Output is correct
25 Correct 316 ms 80068 KB Output is correct
26 Correct 327 ms 80220 KB Output is correct
27 Correct 552 ms 109208 KB Output is correct
28 Correct 416 ms 93592 KB Output is correct
29 Correct 518 ms 105712 KB Output is correct
30 Correct 1046 ms 157980 KB Output is correct
31 Correct 67 ms 75532 KB Output is correct
32 Correct 679 ms 112544 KB Output is correct
33 Correct 790 ms 152748 KB Output is correct
34 Correct 460 ms 148112 KB Output is correct
35 Correct 745 ms 153460 KB Output is correct
36 Correct 444 ms 131984 KB Output is correct
37 Correct 183 ms 88168 KB Output is correct
38 Correct 293 ms 98220 KB Output is correct
39 Correct 1002 ms 163172 KB Output is correct
40 Correct 903 ms 154344 KB Output is correct
41 Correct 187 ms 89404 KB Output is correct
42 Correct 434 ms 110956 KB Output is correct
43 Correct 806 ms 152752 KB Output is correct
44 Correct 435 ms 148080 KB Output is correct
45 Correct 717 ms 153464 KB Output is correct
46 Correct 447 ms 132044 KB Output is correct
47 Correct 176 ms 85788 KB Output is correct
48 Correct 314 ms 101584 KB Output is correct
49 Correct 756 ms 154400 KB Output is correct
50 Correct 658 ms 151840 KB Output is correct
51 Correct 755 ms 157944 KB Output is correct
52 Correct 989 ms 163144 KB Output is correct
53 Correct 895 ms 154348 KB Output is correct
54 Correct 210 ms 89512 KB Output is correct
55 Correct 387 ms 110968 KB Output is correct
56 Correct 819 ms 152724 KB Output is correct
57 Correct 458 ms 148140 KB Output is correct
58 Correct 719 ms 153464 KB Output is correct
59 Correct 443 ms 131912 KB Output is correct
60 Correct 178 ms 85804 KB Output is correct
61 Correct 316 ms 101568 KB Output is correct
62 Correct 762 ms 154488 KB Output is correct
63 Correct 668 ms 151856 KB Output is correct
64 Correct 732 ms 157968 KB Output is correct
65 Correct 954 ms 142460 KB Output is correct
66 Correct 1603 ms 189304 KB Output is correct
67 Correct 1539 ms 186932 KB Output is correct
68 Correct 1240 ms 162064 KB Output is correct
69 Correct 1240 ms 156952 KB Output is correct
70 Correct 120 ms 79016 KB Output is correct
71 Correct 1510 ms 189216 KB Output is correct
72 Correct 1542 ms 186500 KB Output is correct
73 Correct 1255 ms 161940 KB Output is correct
74 Correct 1558 ms 182504 KB Output is correct
75 Correct 1405 ms 189172 KB Output is correct
76 Correct 1405 ms 186504 KB Output is correct
77 Correct 1178 ms 161928 KB Output is correct
78 Correct 1146 ms 163264 KB Output is correct
79 Correct 1363 ms 166448 KB Output is correct
80 Correct 1306 ms 157652 KB Output is correct
81 Correct 467 ms 92804 KB Output is correct
82 Correct 650 ms 114396 KB Output is correct
83 Correct 1093 ms 156184 KB Output is correct
84 Correct 705 ms 151624 KB Output is correct
85 Correct 1066 ms 157052 KB Output is correct
86 Correct 729 ms 135548 KB Output is correct
87 Correct 323 ms 89280 KB Output is correct
88 Correct 490 ms 105156 KB Output is correct
89 Correct 924 ms 157884 KB Output is correct
90 Correct 1020 ms 155548 KB Output is correct
91 Correct 941 ms 161456 KB Output is correct