제출 #230222

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
230222		lyc	무지개나라 (APIO17_rainbow)	C++14	100 / 100	1461 ms	179992 KiB

rainbow

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

#define TRACE(x) cout << #x << " :: " << x << '\n'
#define _ << " " <<
#define FOR(i,a,b) for (int i=(a); i<=(b); ++i)
#define RFOR(i,a,b) for (int i=(a); i>=(b); --i)
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(), (x).end()

struct node {
    int s, e, m; vector<int> v;
    node *l, *r;
    node(int s, int e): s(s), e(e), m((s+e)/2) {
        if (s != e) l = new node(s,m), r = new node(m+1,e);
    }

    void add(int x, int z) {
        if (s == e) { v.push_back(z); return; }
        else if (x <= m) l->add(x,z);
        else r->add(x,z);
    }

    vector<int>& build() {
        if (s != e) {
            auto a = l->build(), b = r->build();
            for (int i = 0, j = 0; i < SZ(a) || j < SZ(b); ) {
                if (i < SZ(a) && (j == SZ(b) || a[i] < b[j])) v.push_back(a[i++]);
                else v.push_back(b[j++]);
            }
        }
        return v;
    }

    int query(int x, int y, int a, int b) {
        if (x > y || a > b) return 0;
        if (s == x && e == y) { return lower_bound(ALL(v),b+1)-lower_bound(ALL(v),a); }
        if (y <= m) return l->query(x,y,a,b);
        if (x > m) return r->query(x,y,a,b);
        return l->query(x,m,a,b) + r->query(m+1,y,a,b);
    }
} *grid, *horz, *vert, *face;

void init(int R, int C, int sr, int sc, int M, char *S) {
    grid = new node(1,R+1);
    horz = new node(1,R+1);
    vert = new node(1,R+1);
    face = new node(1,R+1);

    using ii = pair<int,int>;
    vector<ii> gset, vset, hset, fset;
    gset.emplace_back(sr,sc);
    vset.emplace_back(sr,sc);
    vset.emplace_back(sr+1,sc);
    hset.emplace_back(sr,sc);
    hset.emplace_back(sr,sc+1);
    fset.emplace_back(sr,sc);
    fset.emplace_back(sr+1,sc);
    fset.emplace_back(sr,sc+1);
    fset.emplace_back(sr+1,sc+1);
    FOR(i,0,M-1){
        switch (S[i]) {
            case 'N':
                --sr;
                break;
            case 'S':
                ++sr;
                break;
            case 'E':
                ++sc;
                break;
            case 'W':
                --sc;
                break;
        }
        gset.emplace_back(sr,sc);
        vset.emplace_back(sr,sc);
        vset.emplace_back(sr+1,sc);
        hset.emplace_back(sr,sc);
        hset.emplace_back(sr,sc+1);
        fset.emplace_back(sr,sc);
        fset.emplace_back(sr+1,sc);
        fset.emplace_back(sr,sc+1);
        fset.emplace_back(sr+1,sc+1);
    }

    sort(ALL(gset)); gset.resize(unique(ALL(gset))-gset.begin());
    sort(ALL(hset)); hset.resize(unique(ALL(hset))-hset.begin());
    sort(ALL(vset)); vset.resize(unique(ALL(vset))-vset.begin());
    sort(ALL(fset)); fset.resize(unique(ALL(fset))-fset.begin());
    for (auto& x : gset) grid->add(x.first,x.second);
    for (auto& x : hset) horz->add(x.first,x.second);
    for (auto& x : vset) vert->add(x.first,x.second);
    for (auto& x : fset) face->add(x.first,x.second);
    grid->build();
    horz->build();
    vert->build();
    face->build();
}

int colour(int ar, int ac, int br, int bc) {
    int vb = grid->query(ar,br,ac,bc);
    int conn = vb - grid->query(ar+1,br-1,ac+1,bc-1);

    long long v = (long long)(br-ar+1)*(bc-ac+1) - vb;
    if (v == 0) return 0;
    long long e = (long long)(br-ar+1)*(bc-ac) - horz->query(ar,br,ac+1,bc)
        + (long long)(br-ar)*(bc-ac+1) - vert->query(ar+1,br,ac,bc);
    long long f = (long long)(br-ar)*(bc-ac) - face->query(ar+1,br,ac+1,bc) + 1;

    if (vb > 0 && conn == 0) ++f;
    //TRACE(v _ e _ f _ vb _ conn);
    return v-e+f-1;
}

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