제출 #684895

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
684895		SirCovidThe19th	무지개나라 (APIO17_rainbow)	C++17	100 / 100	1045 ms	205760 KiB

rainbow

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

const int mx = 2e5 + 5;

struct persistentSegTree{
    int idx = 1, root[mx], seg[mx * 31], lc[mx * 31], rc[mx * 31]; set<int> pos[mx];

    void add(int r, int c){
        pos[r].insert(c);
    }
    void init(){
        for (int i = 0; i < mx; i++){
            root[i] = !i ? 0 : root[i - 1];
            for (int j : pos[i]) upd(j, 1, root[i]);
        }
    }
    void dup(int &i){
        lc[idx] = lc[i];
        rc[idx] = rc[i];
        seg[idx] = seg[i];
        i = idx; idx++;
    }
    void upd(int p, int val, int &i, int l = 0, int r = 2e5){
        dup(i);
        if (l == r){ seg[i] += val; return; }

        int mid = (l + r) / 2;
        if (p <= mid) upd(p, val, lc[i], l, mid);
        else upd(p, val, rc[i], mid + 1, r);

        seg[i] = seg[lc[i]] + seg[rc[i]];
    }
    int qry(int ql, int qr, int i, int l = 0, int r = 2e5){
        if (qr < l or ql > r or !i) return 0;
        if (l >= ql and r <= qr) return seg[i];
        int mid = (l + r) / 2;
        return qry(ql, qr, lc[i], l, mid) + qry(ql, qr, rc[i], mid + 1, r);
    }
    int rectQry(int ar, int ac, int br, int bc){
        return qry(ac, bc, root[br]) - qry(ac, bc, root[ar - 1]);
    }
};

int mnr = 1e9, mxr, mnc = 1e9, mxc; persistentSegTree rivers, nodes, topEdg, leftEdg;

void init(int R, int C, int sr, int sc, int m, char *S){
    auto addRiver = [&](int r, int c){
        rivers.add(r, c);
        nodes.add(r, c);
        nodes.add(r, c + 1);
        nodes.add(r + 1, c);
        nodes.add(r + 1, c + 1);
        topEdg.add(r, c);
        topEdg.add(r + 1, c);
        leftEdg.add(r, c);
        leftEdg.add(r, c + 1);
        mnr = min(mnr, r); 
        mxr = max(mxr, r);
        mnc = min(mnc, c);
        mxc = max(mxc, c);
    };
    addRiver(sr, sc);

    for (int i = 0; i < m; i++){
        if (S[i] == 'N') sr--;
        if (S[i] == 'S') sr++;
        if (S[i] == 'E') sc++;
        if (S[i] == 'W') sc--;
        addRiver(sr, sc);
    }
    rivers.init();
    nodes.init();
    topEdg.init();
    leftEdg.init();
}
int colour(int ar, int ac, int br, int bc){
    int n = br - ar + 1;
    int m = bc - ac + 1;
    int C = (ar < mnr and br > mxr and ac < mnc and bc > mxc) ? 2 : 1;
    int V = 2 * (n + m) + nodes.rectQry(ar + 1, ac + 1, br, bc);
    int E = topEdg.rectQry(ar + 1, ac, br, bc) + leftEdg.rectQry(ar, ac + 1, br, bc) + 2 * (n + m);
    int F = E - V + C + 1;
    return F - rivers.rectQry(ar, ac, br, bc) - 1; 
}

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