제출 #1177412

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1177412		12345678	무지개나라 (APIO17_rainbow)	C++20	100 / 100	994 ms	477368 KiB

rainbow

#include "rainbow.h"
#include <bits/stdc++.h>

using namespace std;

const int nx=2e5+5, inf=2e5;

int mxr, mnr, mxc, mnc;

struct persist
{
    set<int> s[nx];
    struct node
    {
        int sm;
        node *l, *r;
        node(int sm=0): sm(sm), l(0), r(0){}
    };
    typedef node* pnode;
    pnode rt[nx];
    void build(int l, int r, pnode &k)
    {
        k=new node();
        if (l==r) return;
        int md=(l+r)/2;
        build(l, md, k->l);
        build(md+1, r, k->r);
    }
    void update(int l, int r, pnode &k, pnode t, int idx)
    {
        k=new node(*t);
        if (l==r) return k->sm++, void();
        int md=(l+r)/2;
        if (idx<=md) update(l, md, k->l, t->l, idx);
        else update(md+1, r, k->r, t->r, idx);
        k->sm=k->l->sm+k->r->sm;
    }
    void init()
    {
        build(1, inf, rt[0]);
        for (int i=1; i<=inf; i++)
        {
            rt[i]=rt[i-1];
            for (auto idx:s[i]) update(1, inf, rt[i], rt[i], idx);
        }
    }
    int query(int l, int r, pnode k, int ql, int qr)
    {
        if (qr<l||r<ql||qr<ql) return 0;
        if (ql<=l&&r<=qr) return k->sm;
        int md=(l+r)/2;
        return query(l, md, k->l, ql ,qr)+query(md+1, r, k->r, ql, qr);
    }
    int querysquare(int ar, int ac, int br, int bc)
    {
        return query(1, inf, rt[br], ac, bc)-query(1, inf, rt[ar-1], ac, bc);
    }
} edgver, edghor, vertex, river;

void addnode(int a, int b)
{
    edgver.s[a].insert(b);
    edgver.s[a].insert(b+1);
    edghor.s[a].insert(b);
    edghor.s[a+1].insert(b);
    vertex.s[a].insert(b);
    vertex.s[a].insert(b+1);
    vertex.s[a+1].insert(b);
    vertex.s[a+1].insert(b+1);
    river.s[a].insert(b);
}

void init(int R, int C, int sr, int sc, int M, char *S) {
    mxr=mnr=sr;
    mxc=mnc=sc;
    addnode(sr, sc);
    for (int i=0; i<M; i++)
    {
        if (S[i]=='N') sr--;
        if (S[i]=='S') sr++;
        if (S[i]=='W') sc--;
        if (S[i]=='E') sc++;
        addnode(sr, sc);
        mxr=max(mxr, sr);
        mnr=min(mnr, sr);
        mxc=max(mxc, sc);
        mnc=min(mnc, sc);
    }
    edgver.init();
    edghor.init();
    vertex.init();
    river.init();
}

int colour(int ar, int ac, int br, int bc) {
    int edg=edgver.querysquare(ar, ac+1, br, bc)+edghor.querysquare(ar+1, ac, br, bc);
    int ver=vertex.querysquare(ar+1, ac+1, br, bc);
    int comp=(mnr<=ar||mxr>=br||mnc<=ac||mxc>=bc)?1:2;
    int face=1+comp-ver+edg;
    int rv=river.querysquare(ar, ac, br, bc);
    return face-rv-1;
}

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