Submission #1205803

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205803		Hamed_Ghaffari	Land of the Rainbow Gold (APIO17_rainbow)	C++20	100 / 100	691 ms	273076 KiB

rainbow

#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pii = pair<int, int>;

#define SZ(x) int(x.size())
#define all(x) x.begin(), x.end()
#define pb push_back
#define lc id<<1
#define rc lc|1
#define mid ((l+r)>>1)

struct rectSum {
private:
    int n;
    vector<pii> arr;
    vector<vector<int>> vec;
    vector<vector<int>> cl;
    void build(int l, int r, int id) {
        if(r-l == 1) {
            vec[id].pb(arr[l].second);
            return;
        }
        build(l, mid, lc);
        build(mid, r, rc);
        cl[id].pb(0);
        int i=0, j=0;
        while(i<SZ(vec[lc]) && j<SZ(vec[rc])) {
            if(vec[lc][i]<=vec[rc][j]) {
                vec[id].pb(vec[lc][i++]);
                cl[id].pb(cl[id].back()+1);
            }
            else {
                vec[id].pb(vec[rc][j++]);
                cl[id].pb(cl[id].back());
            }
        }
        while(i<SZ(vec[lc])) {
            vec[id].pb(vec[lc][i++]);
            cl[id].pb(cl[id].back()+1);
        }
        while(j<SZ(vec[rc])) {
            vec[id].pb(vec[rc][j++]);
            cl[id].pb(cl[id].back());
        }
        vec[lc].clear();
        vec[rc].clear();
    }
    int get(int s, int e, int cnt1, int cnt2, int l, int r, int id) {
        if(s>=r || l>=e) return 0;
        if(s<=l && r<=e) return cnt2 - cnt1;
        return get(s, e, cl[id][cnt1], cl[id][cnt2], l, mid, lc)
             + get(s, e, cnt1-cl[id][cnt1], cnt2-cl[id][cnt2], mid, r, rc);
    }
public:
    inline void add(int x, int y) {
        arr.pb({x, y});
    }
    inline void build() {
        sort(all(arr));
        n = SZ(arr);
        if(!n) return;
        vec = vector<vector<int>>(4*n+5);
        cl = vector<vector<int>>(4*n+5);
        build(0, n, 1);
    }
    inline int get(int s1, int e1, int s2, int e2) {
        if(!n) return 0;
        s1 = lower_bound(all(arr), pii(s1, 0))-arr.begin();
        e1 = lower_bound(all(arr), pii(e1, 0))-arr.begin();
        if(s1>=e1) return 0;
        return
        get(s1, e1, lower_bound(all(vec[1]), s2)-vec[1].begin(),
        lower_bound(all(vec[1]), e2)-vec[1].begin(), 0, n, 1);
    }
} v_ds, e_ds, f_ds;

inline bool have(vector<pii> &vec, pii x) {
    int i = lower_bound(all(vec), x)-vec.begin();
    return i<SZ(vec) && vec[i]==x;
}

int mnx=1e9, mxx=-1e9, mny=1e9, mxy=-1e9;
vector<pii> pnt;

void init(int R, int C, int sr, int sc, int M, char *S) {
    for(int i=0; i<M; i++) {
        pnt.pb({sr, sc});
        if(S[i]=='N') sr--;
        else if(S[i]=='W') sc--;
        else if(S[i]=='S') sr++;
        else if(S[i]=='E') sc++;
    }
    pnt.pb({sr, sc});
    sort(all(pnt));
    pnt.resize(unique(all(pnt))-pnt.begin());
    for(auto [x, y] : pnt) {
        v_ds.add(x, y);
        
        bool h0 = have(pnt, {x-1, y-1});
        bool h1 = have(pnt, {x-1, y});
        bool h2 = have(pnt, {x-1, y+1});
        bool h3 = have(pnt, {x, y-1});

        if(!h0 && !h1 && !h3) f_ds.add(x-1, y-1);
        if(!h1 && !h2) f_ds.add(x-1, y);
        if(!h3) f_ds.add(x, y-1);
        f_ds.add(x, y);

        if(!h1) e_ds.add(2*(x-1), 2*(y-1)+1);
        if(!h3) e_ds.add(2*(x-1)+1, 2*(y-1));
        e_ds.add(2*x, 2*y-1);
        e_ds.add(2*x-1, 2*y);

        mnx = min(mnx, x);
        mxx = max(mxx, x);
        mny = min(mny, y);
        mxy = max(mxy, y);
    }
    v_ds.build();
    e_ds.build();
    f_ds.build();
}

int colour(int ar, int ac, int br, int bc) {
    ll V=1ll*(br-ar+1)*(bc-ac+1) - v_ds.get(ar, br+1, ac, bc+1);
    ll E = 1ll*(br-ar+1)*(bc-ac) + 1ll*(br-ar)*(bc-ac+1) - e_ds.get(2*(ar-1)+1, 2*br, 2*(ac-1)+1, 2*bc);
    ll f = 1ll*(br-ar)*(bc-ac) - f_ds.get(ar, br, ac, bc) + 1;
    if(ar<mnx && br>mxx && ac<mny && bc>mxy) f++;
    return V + f - E - 1;
}

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