oj.uz

Submission #579976

# Submission time Handle Problem Language Result Execution time Memory
579976 2022-06-20T12:11:30 Z loggerr Birthday gift (IZhO18_treearray) C++14
56 / 100
 402 ms 262144 KB 
#include "bits/stdc++.h"

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

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 = 4e5 + 10;
const ll Lg = 20;

vll gr[Maxn];
ll up[Lg][Maxn];
ll d[Maxn];

void dfs(ll v, ll p) {
    up[0][v] = p;
    d[v] = d[p] + 1;
    for (ll adj : gr[v]) {
        if (adj == p) continue;
        dfs(adj, v);
    }
}

ll la(ll v, ll k) {
    forn (i, Lg) {
        if (k & (1 << i))
            v = up[i][v];
    }
    return v;
}

ll lca(ll u, ll v) {
    if (d[u] < d[v]) swap(u, v);
    u = la(u, d[u] - d[v]);
    if (u == v)
        return u;
    for (ll i = Lg - 1; i >= 0; --i) {
        if (up[i][u] == up[i][v]) continue;
        u = up[i][u], v = up[i][v];
    }
    return up[0][u];
}

struct seg {
    vector<map<ll, set<ll>>> tr;
    ll n;

    void insert(ll x, ll l, ll r, ll pos, ll val) {
        if (l + 1 == r) {
            tr[x][val].insert(pos);
            return;
        }
        ll m = (l + r) / 2;
        if (pos < m) insert(2 * x + 1, l, m, pos, val);
        else insert(2 * x + 2, m, r, pos, val);
        tr[x][val].insert(pos);
    }

    void insert(ll pos, ll val) {
        insert(0, 0, n, pos, val);
    }

    void erase(ll x, ll l, ll r, ll pos, ll val) {
        if (l + 1 == r) {
            tr[x][val].erase(pos);
            if (tr[x][val].empty()) tr[x].erase(val);
            return;
        }
        ll m = (l + r) / 2;
        if (pos < m) erase(2 * x + 1, l, m, pos, val);
        else erase(2 * x + 2, m, r, pos, val);
        tr[x][val].erase(pos);
        if (tr[x][val].empty()) tr[x].erase(val);
    }

    void erase(ll pos, ll val) {
        erase(0, 0, n, pos, val);
    }

    seg(vll &arr) {
        n = arr.size();
        tr.resize(4 * n);
        forn (i, n) {
            insert(0, 0, n, i, arr[i]);
        }
    }

    ll get(ll x, ll l, ll r, ll ql, ll qr, ll key) {
        if (qr <= l || r <= ql || qr <= ql) return -1;
        if (ql <= l && r <= qr) {
            auto it = tr[x].find(key);
            if (it == tr[x].end()) return -1;
            return (*tr[x][key].begin());
        }
        ll m = (l + r) / 2;
        return max(get(2 * x + 1, l, m, ql, qr, key), get(2 * x + 2, m, r, ql, qr, key));
    }
};

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);
    for (ll i = 1; i < Lg; ++i) {
        forn (v, Maxn) {
            up[i][v] = up[i - 1][up[i - 1][v]];
        }
    }
    vll que(m);
    forn (i, m) {
        cin >> que[i];
        --que[i];
    }
    seg dcV(que);
    vll lcas(m - 1);
    forn (i, m - 1) {
        lcas[i] = lca(que[i], que[i + 1]);
    }
    seg dcL(lcas);
    while (q--) {
        ll tp;
        cin >> tp;
        if (tp == 1) {
            ll pos, v;
            cin >> pos >> v;
            --pos, --v;
           dcV.erase(pos, que[pos]);
            if (pos - 1 >= 0) {
                dcL.erase(pos - 1, lcas[pos - 1]);
            }
            if (pos + 1 < m) {
                dcL.erase(pos, lcas[pos]);
            }
            que[pos] = v;
            dcV.insert(pos, que[pos]);
            if (pos - 1 >= 0) {
                lcas[pos - 1] = lca(que[pos - 1], que[pos]);
                dcL.insert(pos - 1, lcas[pos - 1]);
            }
            if (pos + 1 < m) {
                lcas[pos] = lca(que[pos], que[pos + 1]);
                dcL.insert(pos, lcas[pos]);
            }
            continue;
        }
        ll l, r, v;
        cin >> l >> r >> v;
        --l, --r, --v;
        ll id = dcV.get(0, 0, m, l, r + 1, v);
       // debug(1);
        if (id != -1) {
            cout << id + 1 << ' ' << id + 1 << endl;
            continue;
        }
        if (l == r) {
            cout << -1 << ' ' << -1 << endl;
            continue;
        }
        --r;
        id = dcL.get(0, 0, m - 1, l, r + 1, v);
        if (id == -1) {
            cout << -1 << ' ' << -1 << endl;
            continue;
        }
        ll ql = id + 1;
        ll qr = ql + 1;
        cout << ql << ' ' << qr << endl;
    }
    return;
}

int main() {
    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 33 ms 69092 KB n=5
2 Correct 34 ms 69424 KB n=100
3 Correct 33 ms 69384 KB n=100
4 Correct 36 ms 69424 KB n=100
5 Correct 41 ms 69392 KB n=100
6 Correct 35 ms 69384 KB n=100
7 Correct 33 ms 69328 KB n=100
8 Correct 35 ms 69484 KB n=100
9 Correct 33 ms 69348 KB n=100
10 Correct 33 ms 69376 KB n=100
11 Correct 34 ms 69444 KB n=100
12 Correct 34 ms 69324 KB n=100
13 Correct 33 ms 69388 KB n=100
14 Correct 33 ms 69416 KB n=100
15 Correct 34 ms 69364 KB n=100
16 Correct 33 ms 69352 KB n=100
17 Correct 34 ms 69460 KB n=100
18 Correct 35 ms 69428 KB n=100
19 Correct 34 ms 69304 KB n=100
20 Correct 34 ms 69432 KB n=100
21 Correct 31 ms 69432 KB n=100
22 Correct 32 ms 69332 KB n=100
23 Correct 34 ms 69428 KB n=100
24 Correct 34 ms 69368 KB n=100
25 Correct 40 ms 69460 KB n=100
26 Correct 33 ms 69232 KB n=12
27 Correct 34 ms 69360 KB n=100

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 69092 KB n=5
2 Correct 34 ms 69424 KB n=100
3 Correct 33 ms 69384 KB n=100
4 Correct 36 ms 69424 KB n=100
5 Correct 41 ms 69392 KB n=100
6 Correct 35 ms 69384 KB n=100
7 Correct 33 ms 69328 KB n=100
8 Correct 35 ms 69484 KB n=100
9 Correct 33 ms 69348 KB n=100
10 Correct 33 ms 69376 KB n=100
11 Correct 34 ms 69444 KB n=100
12 Correct 34 ms 69324 KB n=100
13 Correct 33 ms 69388 KB n=100
14 Correct 33 ms 69416 KB n=100
15 Correct 34 ms 69364 KB n=100
16 Correct 33 ms 69352 KB n=100
17 Correct 34 ms 69460 KB n=100
18 Correct 35 ms 69428 KB n=100
19 Correct 34 ms 69304 KB n=100
20 Correct 34 ms 69432 KB n=100
21 Correct 31 ms 69432 KB n=100
22 Correct 32 ms 69332 KB n=100
23 Correct 34 ms 69428 KB n=100
24 Correct 34 ms 69368 KB n=100
25 Correct 40 ms 69460 KB n=100
26 Correct 33 ms 69232 KB n=12
27 Correct 34 ms 69360 KB n=100
28 Correct 47 ms 70412 KB n=500
29 Correct 39 ms 70604 KB n=500
30 Correct 38 ms 70612 KB n=500
31 Correct 38 ms 70604 KB n=500
32 Correct 40 ms 70460 KB n=500
33 Correct 38 ms 70640 KB n=500
34 Correct 38 ms 70440 KB n=500
35 Correct 39 ms 70684 KB n=500
36 Correct 37 ms 70348 KB n=500
37 Correct 37 ms 70348 KB n=500
38 Correct 34 ms 70348 KB n=500
39 Correct 35 ms 70388 KB n=500
40 Correct 35 ms 70340 KB n=500
41 Correct 34 ms 70448 KB n=500
42 Correct 37 ms 70408 KB n=500
43 Correct 42 ms 70444 KB n=500
44 Correct 42 ms 70476 KB n=500
45 Correct 44 ms 70348 KB n=500
46 Correct 36 ms 70568 KB n=500
47 Correct 38 ms 70624 KB n=500
48 Correct 36 ms 70432 KB n=500
49 Correct 36 ms 70612 KB n=500
50 Correct 37 ms 70328 KB n=500
51 Correct 38 ms 70656 KB n=500
52 Correct 38 ms 70604 KB n=500
53 Correct 41 ms 70604 KB n=500
54 Correct 39 ms 70668 KB n=500
55 Correct 36 ms 70380 KB n=278
56 Correct 39 ms 70664 KB n=500
57 Correct 40 ms 70564 KB n=500
58 Correct 34 ms 70504 KB n=500

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 69092 KB n=5
2 Correct 34 ms 69424 KB n=100
3 Correct 33 ms 69384 KB n=100
4 Correct 36 ms 69424 KB n=100
5 Correct 41 ms 69392 KB n=100
6 Correct 35 ms 69384 KB n=100
7 Correct 33 ms 69328 KB n=100
8 Correct 35 ms 69484 KB n=100
9 Correct 33 ms 69348 KB n=100
10 Correct 33 ms 69376 KB n=100
11 Correct 34 ms 69444 KB n=100
12 Correct 34 ms 69324 KB n=100
13 Correct 33 ms 69388 KB n=100
14 Correct 33 ms 69416 KB n=100
15 Correct 34 ms 69364 KB n=100
16 Correct 33 ms 69352 KB n=100
17 Correct 34 ms 69460 KB n=100
18 Correct 35 ms 69428 KB n=100
19 Correct 34 ms 69304 KB n=100
20 Correct 34 ms 69432 KB n=100
21 Correct 31 ms 69432 KB n=100
22 Correct 32 ms 69332 KB n=100
23 Correct 34 ms 69428 KB n=100
24 Correct 34 ms 69368 KB n=100
25 Correct 40 ms 69460 KB n=100
26 Correct 33 ms 69232 KB n=12
27 Correct 34 ms 69360 KB n=100
28 Correct 47 ms 70412 KB n=500
29 Correct 39 ms 70604 KB n=500
30 Correct 38 ms 70612 KB n=500
31 Correct 38 ms 70604 KB n=500
32 Correct 40 ms 70460 KB n=500
33 Correct 38 ms 70640 KB n=500
34 Correct 38 ms 70440 KB n=500
35 Correct 39 ms 70684 KB n=500
36 Correct 37 ms 70348 KB n=500
37 Correct 37 ms 70348 KB n=500
38 Correct 34 ms 70348 KB n=500
39 Correct 35 ms 70388 KB n=500
40 Correct 35 ms 70340 KB n=500
41 Correct 34 ms 70448 KB n=500
42 Correct 37 ms 70408 KB n=500
43 Correct 42 ms 70444 KB n=500
44 Correct 42 ms 70476 KB n=500
45 Correct 44 ms 70348 KB n=500
46 Correct 36 ms 70568 KB n=500
47 Correct 38 ms 70624 KB n=500
48 Correct 36 ms 70432 KB n=500
49 Correct 36 ms 70612 KB n=500
50 Correct 37 ms 70328 KB n=500
51 Correct 38 ms 70656 KB n=500
52 Correct 38 ms 70604 KB n=500
53 Correct 41 ms 70604 KB n=500
54 Correct 39 ms 70668 KB n=500
55 Correct 36 ms 70380 KB n=278
56 Correct 39 ms 70664 KB n=500
57 Correct 40 ms 70564 KB n=500
58 Correct 34 ms 70504 KB n=500
59 Correct 55 ms 74824 KB n=2000
60 Correct 62 ms 76120 KB n=2000
61 Correct 63 ms 76012 KB n=2000
62 Correct 71 ms 75900 KB n=2000
63 Correct 61 ms 74876 KB n=2000
64 Correct 59 ms 75960 KB n=2000
65 Correct 56 ms 74932 KB n=2000
66 Correct 61 ms 76108 KB n=2000
67 Correct 61 ms 75340 KB n=2000
68 Correct 59 ms 75980 KB n=2000
69 Correct 45 ms 74876 KB n=2000
70 Correct 44 ms 74852 KB n=2000
71 Correct 46 ms 74864 KB n=2000
72 Correct 46 ms 74788 KB n=2000
73 Correct 47 ms 74856 KB n=2000
74 Correct 52 ms 74700 KB n=1844
75 Correct 45 ms 74872 KB n=2000
76 Correct 55 ms 75136 KB n=2000
77 Correct 56 ms 75124 KB n=2000
78 Correct 62 ms 75068 KB n=2000
79 Correct 55 ms 74928 KB n=2000
80 Correct 60 ms 76064 KB n=2000
81 Correct 63 ms 75964 KB n=2000
82 Correct 56 ms 74836 KB n=2000
83 Correct 59 ms 76044 KB n=2000
84 Correct 59 ms 75048 KB n=2000
85 Correct 63 ms 75884 KB n=2000
86 Correct 67 ms 75820 KB n=2000
87 Correct 57 ms 74880 KB n=2000
88 Correct 59 ms 76096 KB n=2000
89 Correct 63 ms 76148 KB n=2000
90 Correct 57 ms 76236 KB n=2000
91 Correct 48 ms 75124 KB n=2000

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 69092 KB n=5
2 Correct 34 ms 69424 KB n=100
3 Correct 33 ms 69384 KB n=100
4 Correct 36 ms 69424 KB n=100
5 Correct 41 ms 69392 KB n=100
6 Correct 35 ms 69384 KB n=100
7 Correct 33 ms 69328 KB n=100
8 Correct 35 ms 69484 KB n=100
9 Correct 33 ms 69348 KB n=100
10 Correct 33 ms 69376 KB n=100
11 Correct 34 ms 69444 KB n=100
12 Correct 34 ms 69324 KB n=100
13 Correct 33 ms 69388 KB n=100
14 Correct 33 ms 69416 KB n=100
15 Correct 34 ms 69364 KB n=100
16 Correct 33 ms 69352 KB n=100
17 Correct 34 ms 69460 KB n=100
18 Correct 35 ms 69428 KB n=100
19 Correct 34 ms 69304 KB n=100
20 Correct 34 ms 69432 KB n=100
21 Correct 31 ms 69432 KB n=100
22 Correct 32 ms 69332 KB n=100
23 Correct 34 ms 69428 KB n=100
24 Correct 34 ms 69368 KB n=100
25 Correct 40 ms 69460 KB n=100
26 Correct 33 ms 69232 KB n=12
27 Correct 34 ms 69360 KB n=100
28 Correct 47 ms 70412 KB n=500
29 Correct 39 ms 70604 KB n=500
30 Correct 38 ms 70612 KB n=500
31 Correct 38 ms 70604 KB n=500
32 Correct 40 ms 70460 KB n=500
33 Correct 38 ms 70640 KB n=500
34 Correct 38 ms 70440 KB n=500
35 Correct 39 ms 70684 KB n=500
36 Correct 37 ms 70348 KB n=500
37 Correct 37 ms 70348 KB n=500
38 Correct 34 ms 70348 KB n=500
39 Correct 35 ms 70388 KB n=500
40 Correct 35 ms 70340 KB n=500
41 Correct 34 ms 70448 KB n=500
42 Correct 37 ms 70408 KB n=500
43 Correct 42 ms 70444 KB n=500
44 Correct 42 ms 70476 KB n=500
45 Correct 44 ms 70348 KB n=500
46 Correct 36 ms 70568 KB n=500
47 Correct 38 ms 70624 KB n=500
48 Correct 36 ms 70432 KB n=500
49 Correct 36 ms 70612 KB n=500
50 Correct 37 ms 70328 KB n=500
51 Correct 38 ms 70656 KB n=500
52 Correct 38 ms 70604 KB n=500
53 Correct 41 ms 70604 KB n=500
54 Correct 39 ms 70668 KB n=500
55 Correct 36 ms 70380 KB n=278
56 Correct 39 ms 70664 KB n=500
57 Correct 40 ms 70564 KB n=500
58 Correct 34 ms 70504 KB n=500
59 Correct 55 ms 74824 KB n=2000
60 Correct 62 ms 76120 KB n=2000
61 Correct 63 ms 76012 KB n=2000
62 Correct 71 ms 75900 KB n=2000
63 Correct 61 ms 74876 KB n=2000
64 Correct 59 ms 75960 KB n=2000
65 Correct 56 ms 74932 KB n=2000
66 Correct 61 ms 76108 KB n=2000
67 Correct 61 ms 75340 KB n=2000
68 Correct 59 ms 75980 KB n=2000
69 Correct 45 ms 74876 KB n=2000
70 Correct 44 ms 74852 KB n=2000
71 Correct 46 ms 74864 KB n=2000
72 Correct 46 ms 74788 KB n=2000
73 Correct 47 ms 74856 KB n=2000
74 Correct 52 ms 74700 KB n=1844
75 Correct 45 ms 74872 KB n=2000
76 Correct 55 ms 75136 KB n=2000
77 Correct 56 ms 75124 KB n=2000
78 Correct 62 ms 75068 KB n=2000
79 Correct 55 ms 74928 KB n=2000
80 Correct 60 ms 76064 KB n=2000
81 Correct 63 ms 75964 KB n=2000
82 Correct 56 ms 74836 KB n=2000
83 Correct 59 ms 76044 KB n=2000
84 Correct 59 ms 75048 KB n=2000
85 Correct 63 ms 75884 KB n=2000
86 Correct 67 ms 75820 KB n=2000
87 Correct 57 ms 74880 KB n=2000
88 Correct 59 ms 76096 KB n=2000
89 Correct 63 ms 76148 KB n=2000
90 Correct 57 ms 76236 KB n=2000
91 Correct 48 ms 75124 KB n=2000
92 Runtime error 402 ms 262144 KB Execution killed with signal 9
93 Halted 0 ms 0 KB -