Submission #1290586

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290586		hiepsimauhong	Birthday gift (IZhO18_treearray)	C++20	100 / 100	771 ms	194724 KiB

treearray

#include <bits/stdc++.h>

using namespace std;

#define int long long

#define FOR(I, L, R) for(int I(L); I <= (int)R ; ++I)
#define FOD(I, R, L) for(int I(R); I >= (int)L ; --I)
#define FOA(I, A) for(auto &I : A)

#define print(A, L, R) FOR(I, L, R){cout << A[I] <<' ';} cout << '\n';
#define printz(A, L, R) FOR(I, 1, L){FOR(J, 1, R){if(A[I][J] <= -oo / 10) cout << "- "; else cout << A[I][J] << ' ';} cout << '\n';} cout << '\n';
#define prints(A) FOA(I, A) cout << I <<' '; cout << '\n';

#define fs first
#define sd second
#define ii pair<int, int>
#define iii pair<int, ii>
#define all(A) A.begin(), A.end()
#define quickly cin.tie(0) -> ios_base::sync_with_stdio(0);
#define FILE "robot"

const int N = 2e5 + 5;
const int mod = 1e9 + 7;
const int oo = 1e18;

int n, m, q;
int a[N];
vector<int> g[N];
set<int> one[N], two[N];

struct LCA{
        int st[N], en[N], h[N], el;
        ii e[2 * N], rmq[2 * N][20];

        void build(int u, int par){
                st[u] = ++el;
                e[el] = {h[u], u};

                FOA(v, g[u]){
                        if(v == par){
                                continue;
                        }
                        h[v] = h[u] + 1;
                        build(v, u);
                        e[++el] = {h[u], u};
                }
                en[u] = el;
        }

        void buildRMQ(){
                FOR(i, 1, 2 * n - 1){
                        rmq[i][0] = e[i];
                }

                for(int j(1) ; (1 << j) <= 2 * n - 1 ; ++j){
                        for(int i(1) ; i + (1 << j) - 1 <= 2 * n - 1 ; ++i){
                                rmq[i][j] = min(rmq[i + (1 << j - 1)][j - 1], rmq[i][j - 1]);
                        }
                }
        }

        bool acs(int u, int v){
                if(st[v] <= st[u] && st[u] <= en[v]){
                        return 1;
                }
                return 0;
        }

        int get(int u, int v){
                if(u == 0) return v;
                if(v == 0) return u;

                int l = st[u];
                int r = st[v];

                if(l > r) swap(l, r);

                int k = __lg(r - l + 1);

                return min(rmq[l][k], rmq[r - (1 << k) + 1][k]).sd;
        }
} lca;

signed main(){ quickly
        if(fopen(FILE".inp", "r")){
                freopen(FILE".inp", "r", stdin);
                freopen(FILE".out", "w", stdout);
        }

        cin >> n >> m >> q;

        FOR(i, 1, n - 1){
                int u, v;
                cin >> u >> v;

                g[u].push_back(v);
                g[v].push_back(u);
        }

        lca.build(1, -1);
        lca.buildRMQ();

        FOR(i, 1, m){
                cin >> a[i];
        }

        FOR(i, 1, m){
                one[a[i]].insert(i);
        }
        FOR(i, 1, m - 1){
                two[lca.get(a[i], a[i + 1])].insert(i);
        }

        while(q--){
                int type;
                cin >> type;

                if(type == 1){
                        int pos, val;
                        cin >> pos >> val;

                        one[a[pos]].erase(pos);
                        one[val].insert(pos);

                        if(pos > 1){
                                int v = lca.get(a[pos - 1], a[pos]);
                                int u = lca.get(a[pos - 1], val);
                                two[v].erase(pos - 1);
                                two[u].insert(pos - 1);
                        }
                        if(pos < m){
                                int v = lca.get(a[pos], a[pos + 1]);
                                int u = lca.get(val, a[pos + 1]);

                                two[v].erase(pos);
                                two[u].insert(pos);
                        }

                        a[pos] = val;
                }
                else{
                        int l, r, u;
                        cin >> l >> r >> u;

                        auto fi = one[u].lower_bound(l);

                        if(fi != one[u].end() && *fi <= r){
                                cout << *fi <<' ' << *fi << '\n';
                                continue;
                        }

                        auto se = two[u].lower_bound(l);

                        if(se != two[u].end() && *se < r){
                                cout << *se <<' ' << *se + 1 << '\n';
                                continue;
                        }

                        cout << -1 <<' ' << -1 << '\n';
                }
        }
}

Compilation message (stderr)

treearray.cpp: In function 'int main()':
treearray.cpp:87:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |                 freopen(FILE".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
treearray.cpp:88:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |                 freopen(FILE".out", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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