Submission #557163

#	Time	Username	Problem	Language	Result	Execution time	Memory
557163		nutella	Land of the Rainbow Gold (APIO17_rainbow)	C++17	0 / 100	1 ms	468 KiB

rainbow

#include "rainbow.h"

//#define _GLIBCXX_DEBUG

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include <bits/stdc++.h>

using namespace std;

//#include <ext/pb_ds/assoc_container.hpp>
//
//using namespace __gnu_pbds;
//
//template<typename T>
//using ordered_set = tree<T, null_type, less < T>, rb_tree_tag, tree_order_statistics_node_update>;

template<typename T>
using normal_queue = priority_queue<T, vector<T>, greater<>>;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

#define trace(x) cout << #x << ": " << (x) << endl;
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define uniq(x) x.resize(unique(all(x)) - begin(x))
#define sz(s) ((int) size(s))
#define pii pair<int, int>
#define mp(x, y) make_pair(x, y)
#define int128 __int128
#define pb push_back
#define popb pop_back
#define eb emplace_back
#define fi first
#define se second
#define itn int

typedef long long ll;
typedef pair<ll, ll> pll;
typedef long double ld;
typedef double db;
typedef unsigned int uint;


template<typename T>
bool ckmn(T &x, T y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}

template<typename T>
bool ckmx(T &x, T y) {
    if (x < y) {
        x = y;
        return true;
    }
    return false;
}

int bit(int x, int b) {
    return (x >> b) & 1;
}

int rand(int l, int r) { return (int) ((ll) rnd() % (r - l + 1)) + l; }


const ll infL = 3e18;
const int infI = 1000000000 + 7;
const int infM = 0x3f3f3f3f; //a little bigger than 1e9
const ll infML = 0x3f3f3f3f3f3f3f3fLL; //4.5e18

template<typename T>
void make_uniq(vector<T> &v) {
    sort(all(v));
    v.resize(unique(all(v)) - begin(v));
}

struct Fenwick {
    int n;
    vector<vector<int> > ys;
    vector<vector<long long> > f;
    vector<int> nn;
    bool built;

    void fake_add(int x, int y) {
        assert(!built);
        for (int i = x + 1; i <= n; i += i & -i) {
            ys[i].emplace_back(y);
        }
    }

    void build() {
        assert(!built);
        for (int i = 0; i <= n; ++i) {
            sort(ys[i].begin(), ys[i].end());
            ys[i].resize(unique(ys[i].begin(), ys[i].end()) - ys[i].begin());
            nn[i] = ys[i].size();
            f[i].resize(nn[i] + 1);
        }
        built = true;
    }

    void add(int x, int y) {
        assert(built);
        for (int i = x + 1; i <= n; i += i & -i) {
            for (int j = lower_bound(ys[i].begin(), ys[i].end(), y) - ys[i].begin() + 1; j <= nn[i]; j += j & -j) {
                f[i][j] += 1;
            }
        }
    }

    long long get(int x, int y) {
        assert(built);

        long long res = 0;
        for (int i = x; i > 0; i -= i & -i) {
            for (int j = lower_bound(ys[i].begin(), ys[i].end(), y) - ys[i].begin(); j > 0; j -= j & -j) {
                res += f[i][j];
            }
        }
        return res;
    }

    long long get(int x1, int y1, int x2, int y2) {
        return get(x2, y2) - get(x1 - 1, y2) - get(x2, y1 - 1) + get(x1 - 1, y1 - 1);
    }

    Fenwick(int n = 0) : n(n), ys(n + 1), f(n + 1), nn(n + 1), built(false) {}
};


const int dx[2] = {0, 1};

const int dy[2] = {1, 0};
int n, m;
vector<pair<int, int>> yy;

Fenwick fx, fy, fv, cv;
int mnx = infI, mny = infI, mxx = -infI, mxy = -infI;

auto here = [](int x, int y) -> bool {
    auto it = lower_bound(all(yy), mp(x, y));
    if (it == end(yy)) return false;
    return (*it) == mp(x, y);
};

void init(int R, int C, int sr, int sc, int M, char *S) {
    n = R, m = C;
    --sr, --sc;
    fx = {n}, fy = {n}, fv = {n}, cv = {n};
    yy = {{sr, sc}};
    for (int i = 0; i < M; ++i) {
        if (S[i] == 'N') --sr;
        else if (S[i] == 'S') ++sr;
        else if (S[i] == 'W') --sc;
        else ++sc;
        yy.emplace_back(sr, sc);
    }
    make_uniq(yy);

    vector<pii > pv, px, py, cvv;
    for (auto [x, y]: yy) { ;
        pv.emplace_back(x, y);
        ckmx(mxx, x);
        ckmx(mxy, y);
        ckmn(mnx, x);
        ckmn(mny, y);
        for (int i = 0; i < 2; ++i) {
            int nx = x + dx[i], ny = y + dy[i];
            if (here(nx, ny)) {
                if (nx == x) {
                    px.emplace_back(x, y);
                } else {
                    py.emplace_back(x, y);
                }
            }
        }
        if (here(x + 1, y) && here(x, y + 1) && here(x + 1, y + 1)) {
            cvv.emplace_back(x, y);
        }
    }

    make_uniq(pv), make_uniq(px), make_uniq(py), make_uniq(cvv);

    for (auto [x, y]: pv)
        fv.fake_add(x, y);
    for (auto [x, y]: px)
        fx.fake_add(x, y);
    for (auto [x, y]: py)
        fy.fake_add(x, y);
    for (auto [x, y]: cvv)
        cv.fake_add(x, y);

    fv.build(), fx.build(), fy.build(), cv.build();

    for (auto [x, y]: pv)
        fv.add(x, y);
    for (auto [x, y]: px)
        fx.add(x, y);
    for (auto [x, y]: py)
        fy.add(x, y);
    for (auto [x, y]: cvv)
        cv.add(x, y);


}

int colour(int ar, int ac, int br, int bc) {
    int x1 = ar, y1 = ac, x2 = br, y2 = bc;
    --x1, --y1;
    --x2, --y2;
    ll C = 1 + bool(x1 < mnx && mxx < x2 && y1 < mny && mxy < y2);
    ll E = (x2 - x1 + 2) * 2 + (y2 - y1 + 2) * 2;
    E += fx.get(x1, y1, x2, y2 - 1) + fy.get(x1, y1, x2 - 1, y2);
    E += fv.get(x1, y2, x2, y2);
    E += fv.get(x1, y1, x2, y1);
    E += fv.get(x1, y1, x1, y2);
    E += fv.get(x2, y1, x2, y2);
    ll V = (x2 - x1 + 2) * 2LL + (y2 - y1 + 2) * 2LL + fv.get(x1, y1, x2, y2);
    ll cnt_squares = fx.get(x1, y1, x1, y2 - 1) + fx.get(x2, y1, x2, y2 - 1) + fy.get(x1, y1, x2 - 1, y1) +
                      fy.get(x1, y2, x2 - 1, y2);
    // .-.
    // | | <---- counted this F extra time
    // O-O
    ll cnt_on_corners = here(x1, y1) + here(x1, y2) + here(x2, y2) + here(x2, y1);
    // .-.
    // | |  <--- nums of Os, so we counted this F extra 1 time
    // .-O
    ll U = cv.get(x1, y1, x2 - 1, y2 - 1) + cnt_on_corners + cnt_squares;
    ll F = C + 1 + E - V;
    ll ans = F - U - 1;
    assert(ans >= 0);
    return (int)ans;
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 12
• Subtask 3: 0 / 24
• Subtask 4: 0 / 27
• Subtask 5: 0 / 26