Submission #566722

#	Time	Username	Problem	Language	Result	Execution time	Memory
566722		hoanghq2004	Land of the Rainbow Gold (APIO17_rainbow)	C++14	100 / 100	1603 ms	189304 KiB

rainbow

#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 (stderr)

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 / 11
• Subtask 2: 12 / 12
• Subtask 3: 24 / 24
• Subtask 4: 27 / 27
• Subtask 5: 26 / 26