제출 #250874

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
250874		receed	무지개나라 (APIO17_rainbow)	C++14	12 / 100	489 ms	70628 KiB

rainbow

#include "rainbow.h"
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cassert>
#include <string>
#include <set>
#include <map>
#include <random>
#include <bitset>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <deque>
#include <queue>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

using namespace std;
using ll = long long;
using ul = unsigned long long;
using ld = long double;

const int N = 1 << 18, M = N * 40;
int tr[M], lv[M], rv[M], sz = 1, rt[N];
set<pair<int, int>> ss, ts;
map<int, vector<int>> mh, mv;
int lx, rx, ly, ry;

int add(int v, int p, int x, int l=0, int r=N) {
    int cv = sz++;
    tr[cv] = tr[v] + x;
    if (r - l == 1)
        lv[cv] = rv[cv] = -1;
    else if (p < (l + r) / 2) {
        lv[cv] = add(lv[v], p, x, l, (l + r) / 2);
        rv[cv] = rv[v];
    }
    else {
        lv[cv] = lv[v];
        rv[cv] = add(rv[v], p, x, (l + r) / 2, r);
    }
    return cv;
}

int sum(int v, int cl, int cr, int l=0, int r=N) {
    if (v == -1 || cr <= l || r <= cl)
        return 0;
    if (cl <= l && r <= cr)
        return tr[v];
    return sum(lv[v], cl, cr, l, (l + r) / 2) + sum(rv[v], cl, cr, (l + r) / 2, r);
}

void init(int r, int c, int sr, int sc, int m, char *s) {
    lx = rx = r;
    ly = ry = c;
    ss.insert({sr, sc});
    rep(i, m) {
        if (s[i] == 'N') sr--;
        else if (s[i] == 'S') sr++;
        else if (s[i] == 'W') sc--;
        else sc++;
        lx = min(lx, sr);
        rx = max(rx, sr);
        ly = min(ly, sc);
        ry = max(ry, sc);
        ss.insert({sr, sc});
    }
    for (auto &p : ss) {
        ts.insert(p);
        if (p.first > 1) {
            ts.insert({p.first - 1, p.second});
            if (p.second > 1)
                ts.insert({p.first - 1, p.second - 1});
        }
        if (p.second > 1)
            ts.insert({p.first, p.second - 1});
    }
    int crt = 0, ls = 0;
    for (auto &p : ts) {
        while (ls < p.first)
            rt[ls++] = crt;
        int val = -1;
        if (ss.count(p)) {
            val += 1;
            if (!ss.count({p.first, p.second + 1}))
                mh[p.first].push_back(p.second);
            if (!ss.count({p.first + 1, p.second}))
                mv[p.second].push_back(p.first);
        }
        else {
            if (ss.count({p.first, p.second + 1}))
                val++;
            if (ss.count({p.first + 1, p.second}))
                val++;
        }
        crt = add(crt, p.second, val);
    }
    for (auto &p : mh)
        sort(all(p.second));
    for (auto &p : mv)
        sort(all(p.second));
}

int colour(int ar, int ac, int br, int bc) {
    ll ans = 1 + sum(rt[br - 1], ac, bc) - sum(rt[ar - 1], ac, bc);
    // cout << ans << '\n';
    if (mh.count(br))
        ans += lower_bound(all(mh[br]), bc) - lower_bound(all(mh[br]), ac);
    if (mv.count(bc))
        ans += lower_bound(all(mv[bc]), br) - lower_bound(all(mv[bc]), ar);
    if (ss.count({br, ac}))
        ans--;
    if (ss.count({ar, bc}))
        ans--;
    if (ss.count({br, bc}))
        ans++;
    if (ar < lx && rx < br && ac < ly && ry < bc)
        ans++;
    return ans;
}

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