Submission #201246

#	Time	Username	Problem	Language	Result	Execution time	Memory
201246		BThero	Land of the Rainbow Gold (APIO17_rainbow)	C++17	100 / 100	2084 ms	133188 KiB

rainbow

// Why am I so dumb? :c
// chrono::system_clock::now().time_since_epoch().count()
                                                  
#include<bits/stdc++.h>
#include "rainbow.h"
//#include<ext/pb_ds/assoc_container.hpp>
//#include<ext/pb_ds/tree_policy.hpp>

#define pb push_back
#define mp make_pair

#define all(x) (x).begin(), (x).end()

#define fi first
#define se second

using namespace std;
//using namespace __gnu_pbds;

typedef long long ll;   
typedef pair<int, int> pii;
//template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const int MAXN = (int)2e5 + 5;
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
const char dc[] = {'E', 'S', 'W', 'N'};

template<int N> struct BIT {
    vector<pii> T[N + 5];

    void update(int x, int y) {
        if (x < 1 || y < 1) {
            return;
        }
        
        int stx = x;

        for (; x <= N; x |= (x + 1)) {
            T[x].pb(mp(y, stx));            
        }
    }

    void build() {
        for (int i = 1; i <= N; ++i) {
            sort(all(T[i]));
            T[i].resize(unique(all(T[i])) - T[i].begin());           
        }
    }

    ll prectS(int x, int ly, int ry) {
        ll ret = 0;
        
        for (; x > 0; --x) {
            ret += lower_bound(all(T[x]), mp(ry + 1, 0)) - lower_bound(all(T[x]), mp(ly, 0));
            x &= (x + 1);
        }

        return ret;
    }

    ll rectS(int ax, int bx, int ay, int by) {
        if (ax > bx || ay > by) {
            return 0;
        }

        return prectS(bx, ay, by) - prectS(ax - 1, ay, by);
    }
};

int mnx, mxx, mny, mxy;

BIT<200000> H[4];

pii arr[MAXN];

int n, m, k;

void init(int R, int C, int stx, int sty, int M, char *S) {
    n = R;
    m = C;
    k = M;
    arr[0] = mp(stx, sty);

    for (int i = 0; i < k; ++i) {
        int dir = find(dc, dc + 4, S[i]) - dc;
        stx += dx[dir];
        sty += dy[dir];
        arr[i + 1] = mp(stx, sty);                                
    }

    mnx = mxx = arr[0].fi;
    mny = mxy = arr[0].se;

    for (int i = 0; i <= k; ++i) {
        int x, y;
        tie(x, y) = arr[i];
        mnx = min(mnx, x);
        mxx = max(mxx, x);
        mny = min(mny, y);
        mxy = max(mxy, y);
        H[0].update(x, y);
        H[1].update(x, y);
        H[1].update(x - 1, y);
        H[2].update(x, y);
        H[2].update(x, y - 1);
        H[3].update(x, y);
        H[3].update(x - 1, y);
        H[3].update(x, y - 1);
        H[3].update(x - 1, y - 1);
    }    

    H[0].build();
    H[1].build();
    H[2].build();
    H[3].build();
}

int colour(int ax, int ay, int bx, int by) {
    ll ans = 1;

    if (ax < mnx && mxx < bx && ay < mny && mxy < by) {
        ++ans;        
    }    

    ans += H[1].rectS(ax, bx - 1, ay, by);
    ans += H[2].rectS(ax, bx, ay, by - 1);
    ans -= H[3].rectS(ax, bx - 1, ay, by - 1);
    ans -= H[0].rectS(ax, bx, ay, by);     
    return ans; 
}

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