제출 #1306961

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1306961		ballbreaker	Birthday gift (IZhO18_treearray)	C++20	100 / 100	1206 ms	127840 KiB

treearray

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,bmi,bmi2,popcnt,lzcnt,sse,sse2,sse3,sse4,tune=native")
#define endl "\n"
// #define int long long
using namespace std;
int tin[200005], tout[200005];
int ord[400005];
vector<int>g[400005];
int timer = 1;
int d[400005];
void dfs(int v, int pr = -1) {
    tin[v] = timer;
    ord[timer] = v;
    timer++;
    for (auto u : g[v]) {
        if (u != pr) {
            d[u] = d[v] + 1;
            dfs(u, v);
            ord[timer] = v;
            timer++;
        }
    }
}
pair<int, int> sp[20][400005];
int logs[400005];
int lca(int a, int b) {
    int l = tin[a];
    int r = tin[b];
    if (l > r) {
        swap(l, r);
    }
    int u = logs[r - l + 1];
    return min(sp[u][l], sp[u][r - (1 << u) + 1]).second;
}
main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, m, q;
    cin >> n >> m >> q;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1);
    logs[0] = -1;
    for (int i = 1; i < timer; i++) {
        sp[0][i] = {d[ord[i]], ord[i]};
        logs[i] = logs[i / 2] + 1;
        // cout << d[ord[i]] << ' ' << ord[i] << endl;
    }
    for (int j = 1; j < 20; j++) {
        // cout << "D " << j << endl;
        for (int i = 1; i + (1 << j) - 1 < timer; i++) {
            sp[j][i] = min(sp[j - 1][i], sp[j - 1][i + (1 << (j - 1))]);
            // cout << sp[j][i].first << ' ' << sp[j][i].second << ' ';
        }
        // cout << endl;
    }
    int a[m + 1];
    map<int, set<int> >lca2;
    map<int, set<int> >lca1;
    for (int i = 1; i <= m; i++) {
        cin >> a[i];
        lca1[a[i]].insert(i);
    }
    for (int i = 2; i <= m; i++) {
        lca2[lca(a[i - 1], a[i])].insert(i);
        // cout << lca(a[i - 1], a[i]) << ' ';
    }
    // cout << endl;
    while (q--) {
        int t;
        cin >> t;
        if (t == 1) {
            int pos, val;
            cin >> pos >> val;
            lca1[a[pos]].erase(pos);
            if (pos > 1) {
                lca2[lca(a[pos - 1], a[pos])].erase(pos);
            }
            if (pos + 1 <= m) {
                lca2[lca(a[pos + 1], a[pos])].erase(pos + 1);
            }
            a[pos] = val;
            lca1[a[pos]].insert(pos);
            if (pos > 1) {
                lca2[lca(a[pos - 1], a[pos])].insert(pos);
            }
            if (pos + 1 <= m) {
                lca2[lca(a[pos + 1], a[pos])].insert(pos + 1);
            }
        } else if (t == 2) {
            int l, r, v;
            cin >> l >> r >> v;
            int ansx = -1, ansy = -1;
            auto it = lca2[v].lower_bound(l + 1);
            if (it != lca2[v].end() && *it <= r) {
                cout << *it - 1 << ' ' << *it << endl;
            } else {
                auto it = lca1[v].lower_bound(l);
                if (it != lca1[v].end() && *it <= r) {
                    cout << *it << ' ' << *it << endl;
                } else {
                    cout << -1 << ' ' << -1 << endl;
                }
            }
        }
    }
    
}

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

treearray.cpp:36:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   36 | main() {
      | ^~~~

• Subtask 1: 12 / 12
• Subtask 2: 18 / 18
• Subtask 3: 26 / 26
• Subtask 4: 44 / 44