Submission #557040

#	Time	Username	Problem	Language	Result	Execution time	Memory
557040		nutella	Land of the Rainbow Gold (APIO17_rainbow)	C++17	0 / 100	3090 ms	336228 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

struct Fenwick {
    unordered_map<int, unordered_map<int, ll>> t;
    int n, m;
    set<pii> stt;

    Fenwick(int a, int b) {
        n = a, m = b;
    }

    Fenwick() = default;

    void build(int a, int b) {
        n = a, m = b;
    }

    void add(int x, int y, int val) {
        if (stt.count(mp(x, y))) return;
        stt.insert(mp(x, y));
        for (int i = x; i < n; i |= (i + 1))
            for (int j = y; j < m; j |= (j + 1))
                t[i][j] += val;
    }

    ll get(int x, int y) {
        ll ans = 0;
        for (int i = x; i > -1; i = ((i + 1) & i) - 1)
            for (int j = y; j > -1; j = ((j + 1) & j) - 1)
                ans += t[i][j];
        return ans;
    }

    ll 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);
    }

};

const int dx[4] = {0, 0, 1, -1};
const int dy[4] = {1, -1, 0, 0};

int n, m;
vector<pair<int, int>>
        river,
        yy;
int mnx = infI, mny = infI, mxx = -infI, mxy = -infI;
Fenwick fx, fy, fv, cv, cx, cy;

void init(int R, int C, int sr, int sc, int M, char *S) {
    n = R + 1, m = C + 1;
    --sr, --sc;
    fx.build(n, m), fy.build(n, m), fv.build(n, m), cv.build(n, m), cx.build(n, m), cy.build(n, m);
    river = {{sr, sc}};
    set<pii > used;
    used.insert(mp(sr, sc));
    for (int i = 0; i < M; ++i) {
        int px = sr, py = sc;
        if (S[i] == 'N') --sr;
        else if (S[i] == 'S') ++sr;
        else if (S[i] == 'W') --sc;
        else ++sc;
        int x = sr, y = sc;
        assert(sr >= 0 && sr < R && sc >= 0 && sc < C);
        river.emplace_back(sr, sc);
        if (!used.count(mp(x, y))) {
            used.insert(mp(x, y));
            if (x == px) {
                cx.add(x, min(py, y), 1);
            } else {
                assert(y == py);
                cy.add(min(x, px), y, 1);
            }
        }
    }
    yy = river;
    sort(all(yy));
    yy.resize(unique(all(yy)) - begin(yy));

    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);
    };

    vector<pair<int, int>>
            pp;

    for (auto [x, y]: yy) {
        cv.add(x, y, 1);
        ckmx(mxx, x);
        ckmn(mnx, x);
        ckmx(mxy, y);
        ckmn(mny, y);
        for (int i = 0; i < 4; ++i) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx >= 0 && ny >= 0 && nx < n && ny < m && !here(nx, ny)) {
                if (nx == x) {
                    fy.add(x, max(ny, y), 1);
                    pp.emplace_back(x, max(ny, y));
                    pp.emplace_back(x + 1, max(ny, y));
                } else {
                    fx.add(max(x, nx), y, 1);
                    pp.emplace_back(max(x, nx), y);
                    pp.emplace_back(max(x, nx), y + 1);
                }
            }
        }
    }

    sort(all(pp));
    pp.resize(unique(all(pp)) - begin(pp));

    for (auto [x, y]: pp) {
        fv.add(x, y, 1);
    }

}

// ans = F - F(river);
// F(river) = C(river) = V(river) - E(river)
// F = C + 1 + E - V
// C is 2 if river is completely inside our rectangle, otherwise C = 1


int colour(int ar, int ac, int br, int bc) {
    int x1 = ar, y1 = ac, x2 = br, y2 = bc;
    --x1, --y1;
    ll rv = cv.get(x1, y1, x2 - 1, y2 - 1);
    ll re = cx.get(x1, y1, x2 - 1, y2 - 2) + cy.get(x1, y1, x2 - 2, y2 - 1);
    ll rf = rv - re;
    assert(rf >= 0);
    bool inside = (rf == 0 ? 0 : x1 + 1 <= mnx && y1 + 1 <= mny && mxx <= x2 - 2 && mxy <= y2 - 2 ? 1 : 0);
    int C = 1;
    if (inside)
        C = 2;
    ll E = (x2 - x1) * 2 + (y2 - y1) * 2 + fx.get(x1 + 1, y1, x2 - 1, y2 - 1) + fy.get(x1, y1 + 1, x2 - 1, y2 - 1);
    ll V = (x2 - x1 + 1) * 2 + (y2 - y1 - 1) * 2 + fv.get(x1 + 1, y1 + 1, x2 - 1, y2 - 1);
    ll F = C + 1 + E - V;
    return (int) (F - rf - 1);
}

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