oj.uz

Submission #579985

# Submission time Handle Problem Language Result Execution time Memory
579985 2022-06-20T12:20:09 Z loggerr Birthday gift (IZhO18_treearray) C++14
56 / 100
 976 ms 262144 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "bits/stdc++.h"

using namespace std;
using ll = int;
using pll = pair<ll, ll>;
using vll = vector<ll>;
using vpl = vector<pll>;
using ld = long double;
using str = string;
using big_int = __int128_t;

const ld eps = 1e-7;
const ld PI = acos(-1);

#define all(c) (c).begin(), (c).end()
#define rall(c) ((c).rbegin()), ((c).rend())
#define ff first
#define ss second
#define pb push_back
#define pf push_front
#define fast ios_base::sync_with_stdio(0); cin.tie(0)
#define forn(i, n) for (ll i = 0; i < n; ++i)
#define sz(a) (ll)a.size()
#define endl '\n'
#define u_map unordered_map
#define mset multiset
//#define x first
//#define y second

#ifdef ONLINE_JUDGE
#define debug(x);
#else
#define debug(x) cerr << #x << ": " << x << endl;
#endif

str IO[2] = {"NO\n", "YES\n"};
str io[2] = {"no\n", "yes\n"};
str Io[2] = {"No\n", "Yes\n"};
//
//mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnd(1232423);

template<class T> bool inmin(T& x_, T y_) {return y_ < x_ ? (x_ = y_, true) : false;}
template<class T> bool inmax(T& x_, T y_) {return y_ > x_ ? (x_ = y_, true) : false;}

//const ll Mod = 1e9 + 7;
const ll Mod = 998244353;
//const ll Mod = 1e9 + 9;
//const ll Mod = 1234567891;
//const ll INF = 1e18;

template<class T> void add(T& x_, T y_) { x_ = (x_ + y_) % Mod; };
template<class T> void sub(T& x_, T y_) { x_ = (x_ + Mod - y_) % Mod; };
template<class T> void mul(T& x_, T y_) { x_ = (x_ * y_) % Mod; };

const ll Maxn = 2e5 + 10;
const ll Lg = 22;

vll gr[Maxn];

ll app[Maxn];
ll st[Lg][Maxn];
ll ans[Lg][Maxn];
ll d[Maxn];
ll dp[Maxn];
vll pth;

void init() {
    dp[0] = -1;
    for (ll i = 1; i < Maxn; ++i) {
        dp[i] = dp[i / 2] + 1;
    }
    return;
}

void dfs(ll v, ll p) {
    app[v] = sz(pth);
    d[v] = d[p] + 1;
    pth.pb(v);
    for (ll adj : gr[v]) {
        if (adj != p) {
            dfs(adj, v);
            pth.pb(v);
        }
    }
    return;
}

ll lca(ll a, ll b) {
    ll l = min(app[a], app[b]);
    ll r = max(app[a], app[b]);
    ll lg = dp[r - l + 1];
    ll len = (1 << lg);
    ll dep = st[lg][l];
    ll res = ans[lg][l];
    if (st[lg][r - len + 1] < dep) {
        return ans[lg][r - len + 1];
    }
    return res;
}
const ll C = 1;

struct block {
    u_map<ll, set<ll>> keys;
    ll size;

    void erase(ll x, ll key) {
        keys[key].erase(x);
    }

    void insert(ll x, ll key) {
        keys[key].insert(x);
    }

    ll get(ll key) {
        return (keys[key].empty() ? -1 : *keys[key].begin());
    }
};

inline void solve() {
    ll n, m, q;
    cin >> n >> m >> q;
    forn (i, n - 1) {
        ll u, v;
        cin >> u >> v;
        --u, --v;
        gr[u].pb(v), gr[v].pb(u);
    }
    dfs(0, 0);
    dfs(0, 0);
    forn (i, sz(pth)) {
        st[0][i] = d[pth[i]];
        ans[0][i] = pth[i];
    }
    for (ll i = 1; i < Lg; ++i) {
        ll len = (1 << i);
        for (ll j = 0; j + len <= sz(pth); ++j) {
            st[i][j] = st[i - 1][j];
            ans[i][j] = ans[i - 1][j];
            if (st[i][j] > st[i - 1][j + len / 2]) {
                st[i][j] = st[i - 1][j + len / 2];
                ans[i][j] = ans[i - 1][j + len / 2];
            }
        }
    }
    vll que(m);
    forn (i, m) {
        cin >> que[i];
        --que[i];
    }
    vll lcas(m - 1);
    forn (i, m - 1) {
        lcas[i] = lca(que[i], que[i + 1]);
    }
    vector<block> dcL;
    forn (i, sz(lcas)) {
        ll id = i / C;
        if (id == sz(dcL)) dcL.pb({});
        dcL[id].size++;
        dcL[id].insert(i, lcas[i]);
    }
    vector<block> dcV;
    forn (i, sz(que)) {
        ll id = i / C;
        if (id == sz(dcV)) dcV.pb({});
        dcV[id].size++;
        dcV[id].insert(i, que[i]);
    }
    auto query = [&](ll l, ll r, ll key, vector<block> &dc, vector<ll> &arr) {
        ll id = -1;
        while (l <= r) {
            if (l % C == 0 && l + dc[l / C].size - 1 <= r) {
                ll nid = dc[l / C].get(key);
                if (nid != -1) id = nid;
                l += dc[l / C].size;
            } else {
                if (arr[l] == key) id = l;
                ++l;
            }
        }
        return id;
    };
    while (q--) {
        ll tp;
        cin >> tp;
        if (tp == 1) {
            ll pos, v;
            cin >> pos >> v;
            --pos, --v;
            dcV[pos / C].erase(pos, que[pos]);
            if (pos - 1 >= 0) {
                dcL[(pos - 1) / C].erase(pos - 1, lcas[pos - 1]);
            }
            if (pos + 1 < m) {
                dcL[pos / C].erase(pos, lcas[pos]);
            }
            que[pos] = v;
            dcV[pos / C].insert(pos, que[pos]);
            if (pos - 1 >= 0) {
                lcas[pos - 1] = lca(que[pos - 1], que[pos]);
                dcL[(pos - 1) / C].insert(pos - 1, lcas[pos - 1]);
            }
            if (pos + 1 < m) {
                lcas[pos] = lca(que[pos], que[pos + 1]);
                dcL[pos / C].insert(pos, lcas[pos]);
            }
            continue;
        }
        ll l, r, v;
        cin >> l >> r >> v;
        --l, --r, --v;
        ll id = query(l, r, v, dcV, que);
        if (id != -1) {
            cout << id + 1 << ' ' << id + 1 << endl;
            continue;
        }
        if (l == r) {
            cout << -1 << ' ' << -1 << endl;
            continue;
        }
        --r;
        id = query(l, r, v, dcL, lcas);
        if (id == -1) {
            cout << -1 << ' ' << -1 << endl;
            continue;
        }
        ll ql = id + 1;
        ll qr = ql + 1;
        cout << ql << ' ' << qr << endl;
    }
    return;
}

int main() {
    init();
    fast;
    //cout << fixed << satprecision(10);
    ll test;
    test = 1;
    //cin >> test;
    for (ll id = 0; id < test; ++id) solve();
    return 0;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5844 KB n=5
2 Correct 4 ms 6228 KB n=100
3 Correct 3 ms 6052 KB n=100
4 Correct 4 ms 5972 KB n=100
5 Correct 5 ms 6004 KB n=100
6 Correct 4 ms 5972 KB n=100
7 Correct 5 ms 5972 KB n=100
8 Correct 4 ms 5972 KB n=100
9 Correct 4 ms 5972 KB n=100
10 Correct 3 ms 5972 KB n=100
11 Correct 4 ms 5972 KB n=100
12 Correct 4 ms 5972 KB n=100
13 Correct 4 ms 5972 KB n=100
14 Correct 4 ms 5972 KB n=100
15 Correct 4 ms 5972 KB n=100
16 Correct 4 ms 5972 KB n=100
17 Correct 5 ms 6100 KB n=100
18 Correct 5 ms 6100 KB n=100
19 Correct 4 ms 5972 KB n=100
20 Correct 4 ms 6100 KB n=100
21 Correct 4 ms 6100 KB n=100
22 Correct 4 ms 5972 KB n=100
23 Correct 4 ms 5972 KB n=100
24 Correct 4 ms 6032 KB n=100
25 Correct 4 ms 5972 KB n=100
26 Correct 4 ms 5924 KB n=12
27 Correct 4 ms 5972 KB n=100

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5844 KB n=5
2 Correct 4 ms 6228 KB n=100
3 Correct 3 ms 6052 KB n=100
4 Correct 4 ms 5972 KB n=100
5 Correct 5 ms 6004 KB n=100
6 Correct 4 ms 5972 KB n=100
7 Correct 5 ms 5972 KB n=100
8 Correct 4 ms 5972 KB n=100
9 Correct 4 ms 5972 KB n=100
10 Correct 3 ms 5972 KB n=100
11 Correct 4 ms 5972 KB n=100
12 Correct 4 ms 5972 KB n=100
13 Correct 4 ms 5972 KB n=100
14 Correct 4 ms 5972 KB n=100
15 Correct 4 ms 5972 KB n=100
16 Correct 4 ms 5972 KB n=100
17 Correct 5 ms 6100 KB n=100
18 Correct 5 ms 6100 KB n=100
19 Correct 4 ms 5972 KB n=100
20 Correct 4 ms 6100 KB n=100
21 Correct 4 ms 6100 KB n=100
22 Correct 4 ms 5972 KB n=100
23 Correct 4 ms 5972 KB n=100
24 Correct 4 ms 6032 KB n=100
25 Correct 4 ms 5972 KB n=100
26 Correct 4 ms 5924 KB n=12
27 Correct 4 ms 5972 KB n=100
28 Correct 5 ms 6512 KB n=500
29 Correct 10 ms 9896 KB n=500
30 Correct 9 ms 9556 KB n=500
31 Correct 13 ms 9960 KB n=500
32 Correct 9 ms 6528 KB n=500
33 Correct 12 ms 9556 KB n=500
34 Correct 6 ms 6484 KB n=500
35 Correct 9 ms 10068 KB n=500
36 Correct 7 ms 6484 KB n=500
37 Correct 10 ms 6484 KB n=500
38 Correct 7 ms 6484 KB n=500
39 Correct 5 ms 6484 KB n=500
40 Correct 5 ms 6484 KB n=500
41 Correct 5 ms 6484 KB n=500
42 Correct 7 ms 6540 KB n=500
43 Correct 7 ms 6524 KB n=500
44 Correct 6 ms 6484 KB n=500
45 Correct 5 ms 6484 KB n=500
46 Correct 9 ms 9944 KB n=500
47 Correct 8 ms 9684 KB n=500
48 Correct 5 ms 6484 KB n=500
49 Correct 10 ms 9812 KB n=500
50 Correct 13 ms 11988 KB n=500
51 Correct 14 ms 12136 KB n=500
52 Correct 15 ms 12884 KB n=500
53 Correct 12 ms 12244 KB n=500
54 Correct 6 ms 6484 KB n=500
55 Correct 6 ms 7380 KB n=278
56 Correct 6 ms 6484 KB n=500
57 Correct 6 ms 6484 KB n=500
58 Correct 6 ms 6484 KB n=500

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5844 KB n=5
2 Correct 4 ms 6228 KB n=100
3 Correct 3 ms 6052 KB n=100
4 Correct 4 ms 5972 KB n=100
5 Correct 5 ms 6004 KB n=100
6 Correct 4 ms 5972 KB n=100
7 Correct 5 ms 5972 KB n=100
8 Correct 4 ms 5972 KB n=100
9 Correct 4 ms 5972 KB n=100
10 Correct 3 ms 5972 KB n=100
11 Correct 4 ms 5972 KB n=100
12 Correct 4 ms 5972 KB n=100
13 Correct 4 ms 5972 KB n=100
14 Correct 4 ms 5972 KB n=100
15 Correct 4 ms 5972 KB n=100
16 Correct 4 ms 5972 KB n=100
17 Correct 5 ms 6100 KB n=100
18 Correct 5 ms 6100 KB n=100
19 Correct 4 ms 5972 KB n=100
20 Correct 4 ms 6100 KB n=100
21 Correct 4 ms 6100 KB n=100
22 Correct 4 ms 5972 KB n=100
23 Correct 4 ms 5972 KB n=100
24 Correct 4 ms 6032 KB n=100
25 Correct 4 ms 5972 KB n=100
26 Correct 4 ms 5924 KB n=12
27 Correct 4 ms 5972 KB n=100
28 Correct 5 ms 6512 KB n=500
29 Correct 10 ms 9896 KB n=500
30 Correct 9 ms 9556 KB n=500
31 Correct 13 ms 9960 KB n=500
32 Correct 9 ms 6528 KB n=500
33 Correct 12 ms 9556 KB n=500
34 Correct 6 ms 6484 KB n=500
35 Correct 9 ms 10068 KB n=500
36 Correct 7 ms 6484 KB n=500
37 Correct 10 ms 6484 KB n=500
38 Correct 7 ms 6484 KB n=500
39 Correct 5 ms 6484 KB n=500
40 Correct 5 ms 6484 KB n=500
41 Correct 5 ms 6484 KB n=500
42 Correct 7 ms 6540 KB n=500
43 Correct 7 ms 6524 KB n=500
44 Correct 6 ms 6484 KB n=500
45 Correct 5 ms 6484 KB n=500
46 Correct 9 ms 9944 KB n=500
47 Correct 8 ms 9684 KB n=500
48 Correct 5 ms 6484 KB n=500
49 Correct 10 ms 9812 KB n=500
50 Correct 13 ms 11988 KB n=500
51 Correct 14 ms 12136 KB n=500
52 Correct 15 ms 12884 KB n=500
53 Correct 12 ms 12244 KB n=500
54 Correct 6 ms 6484 KB n=500
55 Correct 6 ms 7380 KB n=278
56 Correct 6 ms 6484 KB n=500
57 Correct 6 ms 6484 KB n=500
58 Correct 6 ms 6484 KB n=500
59 Correct 19 ms 8788 KB n=2000
60 Correct 217 ms 65400 KB n=2000
61 Correct 208 ms 65228 KB n=2000
62 Correct 159 ms 53660 KB n=2000
63 Correct 25 ms 8916 KB n=2000
64 Correct 208 ms 60640 KB n=2000
65 Correct 24 ms 8600 KB n=2000
66 Correct 213 ms 68940 KB n=2000
67 Correct 36 ms 13680 KB n=2000
68 Correct 204 ms 66416 KB n=2000
69 Correct 61 ms 8376 KB n=2000
70 Correct 65 ms 8376 KB n=2000
71 Correct 67 ms 8376 KB n=2000
72 Correct 23 ms 8404 KB n=2000
73 Correct 21 ms 8276 KB n=2000
74 Correct 16 ms 8532 KB n=1844
75 Correct 24 ms 8360 KB n=2000
76 Correct 49 ms 8516 KB n=2000
77 Correct 38 ms 8484 KB n=2000
78 Correct 41 ms 8444 KB n=2000
79 Correct 18 ms 8504 KB n=2000
80 Correct 171 ms 60100 KB n=2000
81 Correct 130 ms 53988 KB n=2000
82 Correct 12 ms 8460 KB n=2000
83 Correct 155 ms 60392 KB n=2000
84 Correct 274 ms 102724 KB n=2000
85 Correct 336 ms 99840 KB n=2000
86 Correct 296 ms 105420 KB n=2000
87 Correct 312 ms 106628 KB n=2000
88 Correct 46 ms 8644 KB n=2000
89 Correct 50 ms 8532 KB n=2000
90 Correct 33 ms 8684 KB n=2000
91 Correct 34 ms 8348 KB n=2000

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5844 KB n=5
2 Correct 4 ms 6228 KB n=100
3 Correct 3 ms 6052 KB n=100
4 Correct 4 ms 5972 KB n=100
5 Correct 5 ms 6004 KB n=100
6 Correct 4 ms 5972 KB n=100
7 Correct 5 ms 5972 KB n=100
8 Correct 4 ms 5972 KB n=100
9 Correct 4 ms 5972 KB n=100
10 Correct 3 ms 5972 KB n=100
11 Correct 4 ms 5972 KB n=100
12 Correct 4 ms 5972 KB n=100
13 Correct 4 ms 5972 KB n=100
14 Correct 4 ms 5972 KB n=100
15 Correct 4 ms 5972 KB n=100
16 Correct 4 ms 5972 KB n=100
17 Correct 5 ms 6100 KB n=100
18 Correct 5 ms 6100 KB n=100
19 Correct 4 ms 5972 KB n=100
20 Correct 4 ms 6100 KB n=100
21 Correct 4 ms 6100 KB n=100
22 Correct 4 ms 5972 KB n=100
23 Correct 4 ms 5972 KB n=100
24 Correct 4 ms 6032 KB n=100
25 Correct 4 ms 5972 KB n=100
26 Correct 4 ms 5924 KB n=12
27 Correct 4 ms 5972 KB n=100
28 Correct 5 ms 6512 KB n=500
29 Correct 10 ms 9896 KB n=500
30 Correct 9 ms 9556 KB n=500
31 Correct 13 ms 9960 KB n=500
32 Correct 9 ms 6528 KB n=500
33 Correct 12 ms 9556 KB n=500
34 Correct 6 ms 6484 KB n=500
35 Correct 9 ms 10068 KB n=500
36 Correct 7 ms 6484 KB n=500
37 Correct 10 ms 6484 KB n=500
38 Correct 7 ms 6484 KB n=500
39 Correct 5 ms 6484 KB n=500
40 Correct 5 ms 6484 KB n=500
41 Correct 5 ms 6484 KB n=500
42 Correct 7 ms 6540 KB n=500
43 Correct 7 ms 6524 KB n=500
44 Correct 6 ms 6484 KB n=500
45 Correct 5 ms 6484 KB n=500
46 Correct 9 ms 9944 KB n=500
47 Correct 8 ms 9684 KB n=500
48 Correct 5 ms 6484 KB n=500
49 Correct 10 ms 9812 KB n=500
50 Correct 13 ms 11988 KB n=500
51 Correct 14 ms 12136 KB n=500
52 Correct 15 ms 12884 KB n=500
53 Correct 12 ms 12244 KB n=500
54 Correct 6 ms 6484 KB n=500
55 Correct 6 ms 7380 KB n=278
56 Correct 6 ms 6484 KB n=500
57 Correct 6 ms 6484 KB n=500
58 Correct 6 ms 6484 KB n=500
59 Correct 19 ms 8788 KB n=2000
60 Correct 217 ms 65400 KB n=2000
61 Correct 208 ms 65228 KB n=2000
62 Correct 159 ms 53660 KB n=2000
63 Correct 25 ms 8916 KB n=2000
64 Correct 208 ms 60640 KB n=2000
65 Correct 24 ms 8600 KB n=2000
66 Correct 213 ms 68940 KB n=2000
67 Correct 36 ms 13680 KB n=2000
68 Correct 204 ms 66416 KB n=2000
69 Correct 61 ms 8376 KB n=2000
70 Correct 65 ms 8376 KB n=2000
71 Correct 67 ms 8376 KB n=2000
72 Correct 23 ms 8404 KB n=2000
73 Correct 21 ms 8276 KB n=2000
74 Correct 16 ms 8532 KB n=1844
75 Correct 24 ms 8360 KB n=2000
76 Correct 49 ms 8516 KB n=2000
77 Correct 38 ms 8484 KB n=2000
78 Correct 41 ms 8444 KB n=2000
79 Correct 18 ms 8504 KB n=2000
80 Correct 171 ms 60100 KB n=2000
81 Correct 130 ms 53988 KB n=2000
82 Correct 12 ms 8460 KB n=2000
83 Correct 155 ms 60392 KB n=2000
84 Correct 274 ms 102724 KB n=2000
85 Correct 336 ms 99840 KB n=2000
86 Correct 296 ms 105420 KB n=2000
87 Correct 312 ms 106628 KB n=2000
88 Correct 46 ms 8644 KB n=2000
89 Correct 50 ms 8532 KB n=2000
90 Correct 33 ms 8684 KB n=2000
91 Correct 34 ms 8348 KB n=2000
92 Runtime error 976 ms 262144 KB Execution killed with signal 9
93 Halted 0 ms 0 KB -