제출 #1108511

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

rainbow

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

#define MOD 1000000007
#define fir first
#define sec second
#define pushf push_front
#define pushb push_back
#define popf pop_front
#define popb pop_back
#define mp make_pair
#define all(a) a.begin(), a.end()

#define FOR(i, s, e) for(int i = s; i < e; i++)
#define RFOR(i, s, e) for(int i = e-1; i >= s; i--)
#define REP(i, n) FOR(i, 0, n)
#define RREP(i, n) RFOR(i, 0, n)

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef vector<vb> vvb;
typedef vector<vc> vvc;
typedef vector<vpii> vvpii;
typedef vector<vpll> vvpll;
typedef queue<int> qi;
typedef queue<ll> qll;
typedef queue<pii> qpii;
typedef queue<pll> qpll;
typedef deque<int> dqi;
typedef deque<ll> dqll;
typedef deque<pii> dqpii;
typedef deque<pll> dqpll;
typedef priority_queue<int> pqi;
typedef priority_queue<ll> pqll;
typedef priority_queue<pii> pqpii;
typedef priority_queue<pll> pqpll;
typedef priority_queue<int, vi, greater<int> > r_pqi;
typedef priority_queue<ll, vll, greater<ll> > r_pqll;
typedef priority_queue<pii, vpii, greater<pii> > r_pqpii;
typedef priority_queue<pll, vpll, greater<pll> > r_pqpll;
const int maxn = 2e5 + 5;

int R, C;

struct BIT
{
    vi com[maxn], pre[maxn];
    BIT() {}
    void update(int x, int y)
    {
        for (int i = x; i <= R; i += (i & (-i)))
            com[i].pushb(y);
    }
    void build(int x)
    {
        sort(com[x].begin(), com[x].end());
        vector<int> cur = com[x];
        com[x].clear();
        for (int y : cur)
        {
            if (com[x].empty() || com[x].back() != y)
            {
                com[x].pushb(y);
                pre[x].pushb(1);
            }
            else
                pre[x].back()++;
        }
        for (int i = 1; i < (int)com[x].size(); i++)
            pre[x][i] += pre[x][i - 1];
    }
    void init(vpii &A)
    {
        sort(A.begin(), A.end());
        A.erase(unique(A.begin(), A.end()), A.end());
        for (auto [x, y] : A)
            update(x, y);
        for (int i = 1; i <= R; i++)
            build(i);
    }
    int query(int x, int y)
    {
        int res = 0;
        for (int i = x; i >= 1; i -= (i & (-i)))
        {
            int pos = upper_bound(com[i].begin(), com[i].end(), y) - com[i].begin() - 1;
            res += (pos < 0 ? 0 : pre[i][pos]);
        }
        return res;
    }
    int get(int sx, int sy, int tx, int ty)
    {
        return query(tx, ty) - query(tx, sy - 1) - query(sx - 1, ty) + query(sx - 1, sy - 1);
    }
} g, p, cc, rw;

void init(int _R, int _C, int x, int y, int M, char *S)
{
    vector<pii> row, col, G, P;
    R = _R + 1;
    C = _C + 1;
    for (int i = 0; i <= M; i++)
    {
        G.pushb({x, y});
        for (int a = 0; a <= 1; a++)
            for (int b = 0; b <= 1; b++)
            {
                P.pushb({x + a, y + b});
                if (!b)
                    row.pushb({x + a, y + b});
                if (!a)
                    col.pushb({x + a, y + b});
            }
        // cout << x << ' ' << y << '\n';
        if (i == M)
            break;
        if (S[i] == 'N')
            x--;
        else if (S[i] == 'S')
            x++;
        else if (S[i] == 'W')
            y--;
        else
            y++;
    }
    g.init(G);
    p.init(P);
    rw.init(row);
    cc.init(col);
}

int colour(int ar, int ac, int br, int bc)
{
    int V = p.get(ar + 1, ac + 1, br, bc);
    int E = rw.get(ar + 1, ac, br, bc) + cc.get(ar, ac + 1, br, bc);
    int total = g.get(ar, ac, br, bc), mid = 0;
    if (ar + 2 <= br && ac + 2 <= bc)
        mid = g.get(ar + 1, ac + 1, br - 1, bc - 1);
    int CC = 1;
    if (V >= 1 && total == mid)
        CC++;
    // cout << E << ' ' << V << ' ' << CC << ' ' << total << '\n';
    return E - V + CC - total;
}

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

rainbow.cpp: In member function 'void BIT::init(vpii&)':
rainbow.cpp:86:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   86 |         for (auto [x, y] : A)
      |                   ^

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