제출 #678866

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

rainbow

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

using namespace std;
typedef long long ll;
constexpr int INF = 1e9+100;

struct Node{
    int l, r, x;
    Node(){}
    Node(int _l, int _r, int _x): l(_l), r(_r), x(_x) {}
};

struct PST{
    vector<Node> tree;
    vector<int> root;
    int sz;

    int cp(int x){
        tree.push_back(tree[x]);
        return (int)tree.size()-1;
    }
    void update(int i, int l, int r, int p, int x){
        tree[i].x += x;
        if (l==r) return;

        int m = (l+r)>>1;

        if (p <= m){
            tree[i].l = cp(tree[i].l);
            update(tree[i].l, l, m, p, x);
        }
        else{
            tree[i].r = cp(tree[i].r);
            update(tree[i].r, m+1, r, p, x);
        }
    }
    int query(int i, int l, int r, int s, int e){
        if (r<s || e<l) return 0;
        if (s<=l && r<=e) return tree[i].x;

        int m = (l+r)>>1;
        return query(tree[i].l, l, m, s, e) + query(tree[i].r, m+1, r, s, e);
    }

    void init(int n){
        sz = n;
        tree.emplace_back(0, 0, 0);
        root.push_back(0);
    }
    void add_root(){root.push_back(cp(root.back()));}
    void update(int p, int x){update(root.back(), 1, sz, p, x);}
    int query(int t, int l, int r){return query(root[t], 1, sz, l, r);}
    int query2D(int t1, int t2, int l, int r){return query(t2, l, r) - query(t1-1, l, r);}

}treeV, treeEh, treeEv, treeF;

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}, n, m, mnx, mxx, mny, mxy;
vector<int> V[200200], Eh[200200], Ev[200200], F[200200];

void add_vertex(int x, int y){
    mnx = min(mnx, x);
    mxx = max(mxx, x);
    mny = min(mny, y);
    mxy = max(mxy, y);

    V[x].push_back(y);

    Eh[x].push_back(y-1);
    Eh[x].push_back(y);
    Ev[x-1].push_back(y);
    Ev[x].push_back(y);

    for (int i=-1;i<=0;i++){
        for (int j=-1;j<=0;j++){
            F[x+i].push_back(y+j);
        }
    }
}

void pst_init(vector<int> a[], PST &tree){
    tree.init(m);
    for (int i=1;i<=n;i++){
        sort(a[i].begin(), a[i].end());
        a[i].erase(unique(a[i].begin(), a[i].end()), a[i].end());

        tree.add_root();
        for (auto &y:a[i]) if (y>0) tree.update(y, 1);
    }
}

void init(int R, int C, int sr, int sc, int M, char *S) {
    n = R, m = C;
    mnx = mny = 1e9;
    mxx = mxy = -1e9;
    add_vertex(sr, sc);

    for (int i=0;i<M;i++){
        int k;
        if (S[i]=='N') k = 0;
        if (S[i]=='E') k = 1;
        if (S[i]=='S') k = 2;
        if (S[i]=='W') k = 3;

        sr += dx[k], sc += dy[k];
        add_vertex(sr, sc);
    }

    pst_init(V, treeV);
    pst_init(Eh, treeEh);
    pst_init(Ev, treeEv);
    pst_init(F, treeF);
}


int colour(int ar, int ac, int br, int bc) {
    ll v = 0, e = 0, f = 0;
    if (ar < mnx && mxx < br && ac < mny && mxy < bc) f = 1;

    ll xL = br - ar, yL = bc - ac;

    v = xL * yL - treeV.query2D(ar, br, ac, bc);
    e = xL * (yL-1) - treeEh.query2D(ar, br, ac, bc-1);
    e += (xL-1) * yL - treeEv.query2D(ar, br-1, ac, bc);
    f += (xL-1) * (yL-1) - treeF.query2D(ar, br-1, ac, bc-1);

    return v - e + f;
}

컴파일 시 표준 에러 (stderr) 메시지

rainbow.cpp: In function 'void init(int, int, int, int, int, char*)':
rainbow.cpp:105:32: warning: 'k' may be used uninitialized in this function [-Wmaybe-uninitialized]
  105 |         sr += dx[k], sc += dy[k];
      |                            ~~~~^

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