제출 #1205798

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1205798		Hamed_Ghaffari	무지개나라 (APIO17_rainbow)	C++20	12 / 100	350 ms	96368 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, tot_ds;

inline int cnt(vector<pii> &vec, pii s, pii e) {
    return lower_bound(all(vec), e)-lower_bound(all(vec), s);
}

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

vector<pii> hor, ver, hor2, ver2;

void init(int R, int C, int sr, int sc, int M, char *S) {
    for(int i=0; i<M; i++) {
        hor.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++;
    }
    hor.pb({sr, sc});
    sort(all(hor));
    hor.resize(unique(all(hor))-hor.begin());
    for(auto [x, y] : hor) {
        ver.pb({y, x});
        bool rgt = have(hor, {x, y+1});
        bool dwn = have(hor, {x+1, y});
        bool dr = have(hor, {x+1, y+1});
        if(rgt) hor2.pb({x, y}), e_ds.add(2*x-1, 2*y);
        if(dwn) ver2.pb({y, x}), e_ds.add(2*x, 2*y-1);
        if(rgt && dwn && dr) v_ds.add(x, y);
        tot_ds.add(x, y);
    }
    v_ds.build();
    e_ds.build();
    tot_ds.build();
    sort(all(ver));
    sort(all(ver2));
}

int colour(int ar, int ac, int br, int bc) {
    ll V=1ll*(br-ar+2)*(bc-ac+2);
    V -= v_ds.get(ar, br, ac, bc);
    V -= cnt(hor2, {ar, ac}, {ar, bc});
    V -= cnt(hor2, {br, ac}, {br, bc});
    V -= cnt(ver2, {ac, ar}, {ac, br});
    V -= cnt(ver2, {bc, ar}, {bc, br});
    V -= have(hor, {ar, ac});
    V -= have(hor, {ar, bc});
    V -= have(hor, {br, ac});
    V -= have(hor, {br, bc});
    ll E = 1ll*(br-ar+1)*(bc-ac+2) + 1ll*(br-ar+2)*(bc-ac+1);
    E -= e_ds.get(2*(ar-1)+1, 2*br, 2*(ac-1)+1, 2*bc);
    int edge = 0;
    edge += cnt(hor, {ar, ac}, {ar, bc+1});
    edge += cnt(hor, {br, ac}, {br, bc+1});
    edge += cnt(ver, {ac, ar}, {ac, br+1});
    edge += cnt(ver, {bc, ar}, {bc, br+1});
    E -= edge;
    ll f = 1ll*(br-ar+1)*(bc-ac+1) + 1;
    int in = tot_ds.get(ar, br+1, ac, bc+1);
    f -= in;
    if(in && !edge) f++;
    return V + f - E - 1;
}

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