Submission #1189777

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189777		user192837	Drawing (CEOI22_drawing)	C++17	100 / 100	478 ms	53300 KiB

Main

#include <bits/stdc++.h>
#define ar array
#define all(x) x.begin(), x.end()
using namespace std;

struct node {
    int mx = 2e9, sm = 0, i = 1e9;
};

const int N = 2e5 + 5;
vector <int> g[N];
vector <ar <int, 2>> exs[N];
node t[N << 2], qx;
int ans[N], s[N], ql, qr, qi, qs, n;
vector <ar <int, 2>> a;

node merge(node a, node b) {
    node res;
    res.sm = a.sm + b.sm;
    if (a.mx < b.mx)
        res.mx = a.mx, res.i = a.i;
    else
        res.mx = b.mx, res.i = b.i;
    return res;
}

void update(int v, int l, int r) {
    if (l == r)
        return t[v] = qx, void();
    int m = l + r >> 1;
    if (qi <= m)
        update(v << 1, l, m);
    else
        update(v << 1 | 1, m + 1, r);
    t[v] = merge(t[v << 1], t[v << 1 | 1]);
}

node get(int v, int l, int r) {
    if (ql <= l && r <= qr)
        return t[v];
    if (ql > r || l > qr)
        return t[0];
    int m = l + r >> 1;
    return merge(get(v << 1, l, m), get(v << 1 | 1, m + 1, r));
}

int bsl(int v, int l, int r) {
    if (l == r)
        return l;
    int m = l + r >> 1;
    if (t[v << 1].sm >= qs)
        return bsl(v << 1, l, m);
    qs -= t[v << 1].sm;
    return bsl(v << 1 | 1, m + 1, r);
}

int bsr(int v, int l, int r) {
    if (l == r)
        return l;
    int m = l + r >> 1;
    if (t[v << 1 | 1].sm >= qs)
        return bsr(v << 1 | 1, m + 1, r);
    qs -= t[v << 1 | 1].sm;
    return bsr(v << 1, l, m);
}

void dfs(int x, int par) {
    s[x] = 1;
    for (int y : g[x])
        if (y != par)
            dfs(y, x), s[x] += s[y];
}

void make(int x, int par, int l, int r) {
    int lf = 1;
    for (int y : g[x]) {
        if (y != par) {
            qs = s[y];
            if (lf)
                make(y, x, 1, bsl(1, 1, n)), lf = 0;
            else
                make(y, x, bsr(1, 1, n), n);
        }
    }
    ql = l, qr = r;
    node now = get(1, 1, n);
    auto nw = a[now.i];
    ans[now.i] = x;
    exs[nw[0]].pop_back();
    qi = nw[0];
    if (exs[nw[0]].empty()) {
        qx = t[0];
    } else {
        qx.sm = 1, qx.mx = exs[nw[0]].back()[0], qx.i = exs[nw[0]].back()[1];
    }
    update(1, 1, n);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n;
    a.assign(n, {0, 0});
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }
    int rt = -1;
    for (int i = 1; i <= n; i++)
        if (g[i].size() == 1)
            rt = i;
    vector <int> xs, ys;
    for (auto &now : a) {
        cin >> now[0] >> now[1];
        xs.emplace_back(now[0]);
        ys.emplace_back(now[1]);
    }
    sort(all(xs));
    sort(all(ys));
    int tmp = 0;
    for (auto &now : a) {
        now[0] = lower_bound(all(xs), now[0]) - xs.begin() + 1;
        now[1] = lower_bound(all(ys), now[1]) - ys.begin() + 1;
        exs[now[0]].push_back({now[1], tmp});
        if (exs[now[0]][0][0] >= now[1]) {
            qi = now[0]; qx.sm = 1, qx.i = tmp, qx.mx = now[1];
            update(1, 1, n);
        } else {
            swap(exs[now[0]][0], exs[now[0]].back());
        }
        tmp++;
    }
    dfs(rt, 0);
    make(rt, 0, 1, n);
    for (int i = 0; i < n; i++)
        cout << ans[i] << ' ';
}

• Subtask 1: 10 / 10
• Subtask 2: 15 / 15
• Subtask 3: 15 / 15
• Subtask 4: 35 / 35
• Subtask 5: 25 / 25