제출 #567472

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
567472		ngpin04	무지개나라 (APIO17_rainbow)	C++14	12 / 100	471 ms	84088 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;

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

    s.insert({sr, sc});
    for (int i = 0; i < M; i++) {
        int dir = fix(S[i]);
        sr += dx[dir];
        sc += dy[dir];
        s.insert({sr, sc});
        // cerr << sr << " " << sc << "\n";
    }

    for (const auto &[x, y] : s) {
        int a = false, b = false;
        if (s.find({x + 1, y}) != s.end()) {
            col.fakeupdate(x + 1, y);
            a = true;
        }
        
        if (s.find({x, y + 1}) != s.end()) {
            row.fakeupdate(x, y + 1);
            b = true;
        }

        if (a && b) {
            if (s.find({x + 1, y + 1}) != s.end()) 
                face.fakeupdate(x + 1, y + 1);
        }

        cell.fakeupdate(x, y);
    }

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

    for (const auto &[x, y] : s) {
        int a = false, b = false;
        if (s.find({x + 1, y}) != s.end()) {
            col.update(x + 1, y);
            a = true;
        }
        
        if (s.find({x, y + 1}) != s.end()) {
            row.update(x, y + 1);
            b = true;
        }

        if (a && b) {
            if (s.find({x + 1, y + 1}) != s.end()) 
                face.update(x + 1, y + 1);
        }

        cell.update(x, y);
    }
}

int colour(int x, int y, int u, int v) {
    int res = 0;
    int V = cell.getsum(x, y, u, v);

    if (V == 0) 
        return 1;

    int E = col.getsum(x + 1, y, u, v) + row.getsum(x, y + 1, u, v);
    int S = 0;
    S += cell.getsum(x, y, x, v);
    S += cell.getsum(x, y, u, y);
    S += cell.getsum(u, y, u, v);
    S += cell.getsum(x, v, u, v);
    maxi(S, 1);
    E += S;

    int F = 0;
    F += face.getsum(x + 1, y + 1, u, v);
    F += row.getsum(x, y + 1, x, v);
    F += row.getsum(u, y + 1, u, v);
    F += col.getsum(x + 1, y, u, y);
    F += col.getsum(x + 1, v, u, v);
    F += s.count({x, y}) + s.count({x, v}) + s.count({u, y}) + s.count({u, v});
    // cerr << V << " " << E << " " << F << "\n";
    return 1 + (E - V - F);
}

//#include "grader.cpp"

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

rainbow.cpp: In function 'void init(int, int, int, int, int, char*)':
rainbow.cpp:105:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  105 |     for (const auto &[x, y] : s) {
      |                      ^
rainbow.cpp:130:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  130 |     for (const auto &[x, y] : s) {
      |                      ^
rainbow.cpp: In function 'int colour(int, int, int, int)':
rainbow.cpp:152:9: warning: unused variable 'res' [-Wunused-variable]
  152 |     int res = 0;
      |         ^~~

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