제출 #567517

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

rainbow

#include <bits/stdc++.h>
#include "rainbow.h"
#define fi first
#define se second
#define mp make_pair
#define TASK ""
#define bit(x) (1LL << (x))
#define getbit(x, i) (((x) >> (i)) & 1)
#define ALL(x) (x).begin(), (x).end() 
using namespace std;
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
    if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
    if (a < b) {a = b; return true;} return false;
}
mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());

int rand(int l, int r) {
    return l + rd() % (r - l + 1);
}
const int N = 1e5 + 5; 
const int oo = 1e9;
const long long ooo = 1e18;
const int mod = 1e9 + 7; // 998244353;
const long double pi = acos(-1);
const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};

struct BIT2D {
    int n;
    vector <vector <int>> val;
    vector <vector <int>> bit;

    BIT2D(int _n = 0) {
        n = _n;
        bit.resize(n + 5);
        val.resize(n + 5);
    }

    void fakeupdate(int x, int y) {
        for (; x <= n; x += x & -x) 
            val[x].push_back(y);
    }

    void build() {
        for (int i = 1; i <= n; i++) {
            sort(ALL(val[i]));
            val[i].resize(unique(ALL(val[i])) - val[i].begin());
            bit[i].resize(val[i].size() + 1);
        }
    }

    void update(int x, int y) {
        for (; x <= n; x += x & -x) {
            int i = lower_bound(ALL(val[x]), y) - val[x].begin() + 1;
            for (; i < (int) bit[x].size(); i += i & -i)
                bit[x][i]++;
        }
    }

    int getsum(int x, int y) {
        int res = 0;
        for (; x; x -= x & -x) {
            int i = upper_bound(ALL(val[x]), y) - val[x].begin();
            for (; i; i -= i & -i)
                res += bit[x][i];
        }
        return res;
    }

    int getsum(int x, int y, int u, int v) {
        if (x > u || y > v)
            return 0;
        return (getsum(u, v) + getsum(x - 1, y - 1)) 
        -      (getsum(u, y - 1) + getsum(x - 1, v));
    }
};

int fix(char c) {
    if (c == 'W') 
        return 3;
    if (c == 'N') 
        return 2;
    if (c == 'E')
        return 1;
    return 0;
}

BIT2D row, col, cell, face;

set <pair <int, int>> s, r, c, f;

int maxx, maxy, minx, miny;

void add(int sr, int sc) {
    s.insert({sr, sc});
    s.insert({sr + 1, sc});
    s.insert({sr, sc + 1});
    s.insert({sr + 1, sc + 1});

    f.insert({sr + 1, sc + 1});
    
    r.insert({sr, sc + 1});
    r.insert({sr + 1, sc + 1});

    c.insert({sr + 1, sc});
    c.insert({sr + 1, sc + 1});

    maxi(maxx, sr);
    maxi(maxy, sc);
    mini(minx, sr);
    mini(miny, sc);
}

void init(int R, int C, int sr, int sc, int M, char *S) {
    row = col = cell = face = BIT2D(R + 1);

    minx = maxx = sr;
    miny = maxy = sc;
    add(sr, sc);
    for (int i = 0; i < M; i++) {
        int dir = fix(S[i]);
        sr += dx[dir];
        sc += dy[dir];
        add(sr, sc);
    }

    for (auto [x, y] : s) 
        cell.fakeupdate(x, y);

    for (auto [x, y] : r) 
        row.fakeupdate(x, y);

    for (auto [x, y] : c)
        col.fakeupdate(x, y);

    for (auto [x, y] : f)
        face.fakeupdate(x, y);


    cell.build();
    row.build();
    col.build();
    face.build();

    for (auto [x, y] : s) 
        cell.update(x, y);

    for (auto [x, y] : r) 
        row.update(x, y);

    for (auto [x, y] : c)
        col.update(x, y);

    for (auto [x, y] : f)
        face.update(x, y);
}

int colour(int x, int y, int u, int v) {
    int C = 1 + (x < minx && maxx < u && y < miny && maxy < v);
    // cerr << minx << " " << maxx << " " << miny << " " << maxy << "\n";
    v++;
    u++;
    int R = face.getsum(x + 1, y + 1, u, v);
    int V = cell.getsum(x + 1, y + 1, u - 1, v - 1);
    int E = row.getsum(x + 1, y + 1, u - 1, v)
        +   col.getsum(x + 1, y + 1, u, v - 1);

    // cerr << V << " " << E << " " << C << " " << R << "\n";
    int F = 1 + (C + E - V);
    return F - R - 1;    
}

//#include "grader.cpp"

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