oj.uz

Submission #91997

# Submission time Handle Problem Language Result Execution time Memory
91997 2018-12-31T21:38:24 Z popovicirobert Birthday gift (IZhO18_treearray) C++14
56 / 100
 913 ms 263168 KB 
#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
#define ld long double
// 217
// 44

using namespace std;

const int MAXN = (int) 2e5;
const int LOG = 19;

vector <int> g[MAXN + 1];
int lvl[MAXN + 1];

int rmq[2 * MAXN + 1][LOG + 1];
int first[MAXN + 1], sz;

void dfs(int nod, int par) {
    rmq[++sz][0] = nod;
    first[nod] = sz;
    lvl[nod] = lvl[par] + 1;
    for(auto it : g[nod]) {
        if(it != par) {
            dfs(it, nod);
            rmq[++sz][0] = nod;
        }
    }
}

char lg[2 * MAXN + 1];

inline void prec(int n) {
    dfs(1, 0);
    for(int i = 2; i <= sz; i++) {
        lg[i] = lg[i >> 1] + 1;
    }
    for(int bit = 1; (1 << bit) <= sz; bit++) {
        for(int i = 1; i + (1 << bit) <= sz + 1; i++) {
            int a = rmq[i][bit - 1], b = rmq[i + (1 << (bit - 1))][bit - 1];
            if(lvl[a] < lvl[b])
                rmq[i][bit] = a;
            else
                rmq[i][bit] = b;
        }
    }
}

inline int get(int x, int y) {
    x = first[x], y = first[y];
    if(x > y) {
        swap(x, y);
    }
    int bit = lg[y - x + 1];
    int a = rmq[x][bit], b = rmq[y - (1 << bit) + 1][bit];
    if(lvl[a] < lvl[b])
        return a;
    return b;
}

int arr[MAXN + 1];

struct SegTree {
    vector < multiset <int> > aint;
    int n;
    SegTree(int _n) {
        n = _n;
        aint.resize(4 * n + 1);
    }
    void update(int nod, int left, int right, int pos, int val, bool type) {
        if(type) {
            aint[nod].insert(val);
        }
        else {
            aint[nod].erase(aint[nod].find(val));
        }
        if(left == right) {
            return ;
        }
        else {
            int mid = (left + right) / 2;
            if(pos <= mid)
                update(2 * nod, left, mid, pos, val, type);
            else
                update(2 * nod + 1, mid + 1, right, pos, val, type);
        }
    }
    pair <bool, int> query(int nod, int left, int right, int l, int r, int val) {
        if(l <= left && right <= r) {
            if(left == right) {
                if(*aint[nod].begin() == val) {
                    return {1, left};
                }
                return {0, 0};
            }
            auto it = aint[nod].find(val);
            pair <int, int> ans = {0, 0};
            if(it != aint[nod].end()) {
                int mid = (left + right) / 2;
                if(aint[2 * nod].find(val) != aint[2 * nod].end()) {
                    ans = query(2 * nod, left, mid, l, r, val);
                }
                else {
                    ans = query(2 * nod + 1, mid + 1, right, l, r, val);
                }
            }
            return ans;
        }
        else {
            int mid = (left + right) / 2;
            pair <int, int> ans = {0, 0};
            if(l <= mid)
                ans = query(2 * nod, left, mid, l, r, val);
            if(mid < r && ans.first == 0) {
                pair <int, int> aux = query(2 * nod + 1, mid + 1, right, l, r, val);
                if(aux.first == 1) {
                    ans = aux;
                }
            }
            return ans;
        }
    }
};

int main() {
    //ifstream cin("A.in");
    //ofstream cout("A.out");
    int i, n, m, q;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> m >> q;
    for(i = 1; i < n; i++) {
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    prec(n);
    for(i = 1; i<= m; i++) {
        cin >> arr[i];
    }
    SegTree segt1(m), segt2(m);
    for(i = 1; i <= m; i++) {
        segt1.update(1, 1, m, i, arr[i], 1);
        if(i < m) {
            segt2.update(1, 1, m, i, get(arr[i], arr[i + 1]), 1);
        }
    }
    while(q > 0) {
        q--;
        int type;
        cin >> type;
        if(type == 1) {
            int pos, nod;
            cin >> pos >> nod;
            segt1.update(1, 1, m, pos, arr[pos], 0);
            segt1.update(1, 1, m, pos, nod, 1);
            if(pos > 1) {
                segt2.update(1, 1, m, pos - 1, get(arr[pos - 1], arr[pos]), 0);
                segt2.update(1, 1, m, pos - 1, get(arr[pos - 1], nod), 1);
            }
            if(pos < m) {
                segt2.update(1, 1, m, pos, get(arr[pos], arr[pos + 1]), 0);
                segt2.update(1, 1, m, pos, get(nod, arr[pos + 1]), 1);
            }
            arr[pos] = nod;
        }
        else {
            int l, r, nod;
            cin >> l >> r >> nod;
            pair <int, int> ans = {0, 0};
            ans = segt1.query(1, 1, m, l, r, nod);
            if(ans.first == 0) {
                if(l < r) {
                    ans = segt2.query(1, 1, m, l, r - 1, nod);
                }
                if(ans.first) {
                    cout << ans.second << " " << ans.second + 1 << "\n";
                }
                else {
                    cout << -1 << " " << -1 << "\n";
                }
            }
            else {
                cout << ans.second << " " << ans.second << "\n";
            }
        }
    }
    //cin.close();
    //cout.close();
    return 0;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4984 KB n=5
2 Correct 5 ms 5112 KB n=100
3 Correct 5 ms 5112 KB n=100
4 Correct 6 ms 5116 KB n=100
5 Correct 6 ms 5112 KB n=100
6 Correct 6 ms 5240 KB n=100
7 Correct 6 ms 5112 KB n=100
8 Correct 6 ms 5212 KB n=100
9 Correct 6 ms 5112 KB n=100
10 Correct 6 ms 5228 KB n=100
11 Correct 6 ms 5112 KB n=100
12 Correct 6 ms 5112 KB n=100
13 Correct 6 ms 5112 KB n=100
14 Correct 6 ms 5112 KB n=100
15 Correct 6 ms 5112 KB n=100
16 Correct 5 ms 5112 KB n=100
17 Correct 6 ms 5240 KB n=100
18 Correct 6 ms 5240 KB n=100
19 Correct 6 ms 5112 KB n=100
20 Correct 6 ms 5112 KB n=100
21 Correct 6 ms 5112 KB n=100
22 Correct 6 ms 5112 KB n=100
23 Correct 6 ms 5112 KB n=100
24 Correct 6 ms 5112 KB n=100
25 Correct 6 ms 5112 KB n=100
26 Correct 6 ms 5112 KB n=12
27 Correct 6 ms 5112 KB n=100

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4984 KB n=5
2 Correct 5 ms 5112 KB n=100
3 Correct 5 ms 5112 KB n=100
4 Correct 6 ms 5116 KB n=100
5 Correct 6 ms 5112 KB n=100
6 Correct 6 ms 5240 KB n=100
7 Correct 6 ms 5112 KB n=100
8 Correct 6 ms 5212 KB n=100
9 Correct 6 ms 5112 KB n=100
10 Correct 6 ms 5228 KB n=100
11 Correct 6 ms 5112 KB n=100
12 Correct 6 ms 5112 KB n=100
13 Correct 6 ms 5112 KB n=100
14 Correct 6 ms 5112 KB n=100
15 Correct 6 ms 5112 KB n=100
16 Correct 5 ms 5112 KB n=100
17 Correct 6 ms 5240 KB n=100
18 Correct 6 ms 5240 KB n=100
19 Correct 6 ms 5112 KB n=100
20 Correct 6 ms 5112 KB n=100
21 Correct 6 ms 5112 KB n=100
22 Correct 6 ms 5112 KB n=100
23 Correct 6 ms 5112 KB n=100
24 Correct 6 ms 5112 KB n=100
25 Correct 6 ms 5112 KB n=100
26 Correct 6 ms 5112 KB n=12
27 Correct 6 ms 5112 KB n=100
28 Correct 10 ms 5756 KB n=500
29 Correct 9 ms 5880 KB n=500
30 Correct 9 ms 5880 KB n=500
31 Correct 9 ms 5752 KB n=500
32 Correct 8 ms 5752 KB n=500
33 Correct 10 ms 5752 KB n=500
34 Correct 8 ms 5752 KB n=500
35 Correct 9 ms 5756 KB n=500
36 Correct 7 ms 5880 KB n=500
37 Correct 7 ms 5752 KB n=500
38 Correct 7 ms 5880 KB n=500
39 Correct 7 ms 5752 KB n=500
40 Correct 8 ms 5752 KB n=500
41 Correct 7 ms 5880 KB n=500
42 Correct 9 ms 5880 KB n=500
43 Correct 10 ms 5852 KB n=500
44 Correct 10 ms 5752 KB n=500
45 Correct 10 ms 5880 KB n=500
46 Correct 9 ms 5880 KB n=500
47 Correct 10 ms 5752 KB n=500
48 Correct 9 ms 5752 KB n=500
49 Correct 10 ms 5880 KB n=500
50 Correct 10 ms 5752 KB n=500
51 Correct 10 ms 5880 KB n=500
52 Correct 10 ms 5880 KB n=500
53 Correct 10 ms 5880 KB n=500
54 Correct 9 ms 5880 KB n=500
55 Correct 7 ms 5752 KB n=278
56 Correct 10 ms 5880 KB n=500
57 Correct 10 ms 5752 KB n=500
58 Correct 8 ms 5880 KB n=500

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4984 KB n=5
2 Correct 5 ms 5112 KB n=100
3 Correct 5 ms 5112 KB n=100
4 Correct 6 ms 5116 KB n=100
5 Correct 6 ms 5112 KB n=100
6 Correct 6 ms 5240 KB n=100
7 Correct 6 ms 5112 KB n=100
8 Correct 6 ms 5212 KB n=100
9 Correct 6 ms 5112 KB n=100
10 Correct 6 ms 5228 KB n=100
11 Correct 6 ms 5112 KB n=100
12 Correct 6 ms 5112 KB n=100
13 Correct 6 ms 5112 KB n=100
14 Correct 6 ms 5112 KB n=100
15 Correct 6 ms 5112 KB n=100
16 Correct 5 ms 5112 KB n=100
17 Correct 6 ms 5240 KB n=100
18 Correct 6 ms 5240 KB n=100
19 Correct 6 ms 5112 KB n=100
20 Correct 6 ms 5112 KB n=100
21 Correct 6 ms 5112 KB n=100
22 Correct 6 ms 5112 KB n=100
23 Correct 6 ms 5112 KB n=100
24 Correct 6 ms 5112 KB n=100
25 Correct 6 ms 5112 KB n=100
26 Correct 6 ms 5112 KB n=12
27 Correct 6 ms 5112 KB n=100
28 Correct 10 ms 5756 KB n=500
29 Correct 9 ms 5880 KB n=500
30 Correct 9 ms 5880 KB n=500
31 Correct 9 ms 5752 KB n=500
32 Correct 8 ms 5752 KB n=500
33 Correct 10 ms 5752 KB n=500
34 Correct 8 ms 5752 KB n=500
35 Correct 9 ms 5756 KB n=500
36 Correct 7 ms 5880 KB n=500
37 Correct 7 ms 5752 KB n=500
38 Correct 7 ms 5880 KB n=500
39 Correct 7 ms 5752 KB n=500
40 Correct 8 ms 5752 KB n=500
41 Correct 7 ms 5880 KB n=500
42 Correct 9 ms 5880 KB n=500
43 Correct 10 ms 5852 KB n=500
44 Correct 10 ms 5752 KB n=500
45 Correct 10 ms 5880 KB n=500
46 Correct 9 ms 5880 KB n=500
47 Correct 10 ms 5752 KB n=500
48 Correct 9 ms 5752 KB n=500
49 Correct 10 ms 5880 KB n=500
50 Correct 10 ms 5752 KB n=500
51 Correct 10 ms 5880 KB n=500
52 Correct 10 ms 5880 KB n=500
53 Correct 10 ms 5880 KB n=500
54 Correct 9 ms 5880 KB n=500
55 Correct 7 ms 5752 KB n=278
56 Correct 10 ms 5880 KB n=500
57 Correct 10 ms 5752 KB n=500
58 Correct 8 ms 5880 KB n=500
59 Correct 27 ms 8440 KB n=2000
60 Correct 31 ms 8568 KB n=2000
61 Correct 38 ms 8568 KB n=2000
62 Correct 32 ms 8568 KB n=2000
63 Correct 30 ms 8572 KB n=2000
64 Correct 31 ms 8548 KB n=2000
65 Correct 29 ms 8500 KB n=2000
66 Correct 32 ms 8696 KB n=2000
67 Correct 31 ms 8568 KB n=2000
68 Correct 29 ms 8568 KB n=2000
69 Correct 17 ms 8568 KB n=2000
70 Correct 16 ms 8568 KB n=2000
71 Correct 17 ms 8568 KB n=2000
72 Correct 20 ms 8568 KB n=2000
73 Correct 19 ms 8564 KB n=2000
74 Correct 25 ms 8440 KB n=1844
75 Correct 19 ms 8568 KB n=2000
76 Correct 29 ms 8568 KB n=2000
77 Correct 28 ms 8568 KB n=2000
78 Correct 28 ms 8568 KB n=2000
79 Correct 27 ms 8492 KB n=2000
80 Correct 30 ms 8568 KB n=2000
81 Correct 31 ms 8568 KB n=2000
82 Correct 28 ms 8440 KB n=2000
83 Correct 32 ms 8568 KB n=2000
84 Correct 28 ms 8568 KB n=2000
85 Correct 33 ms 8696 KB n=2000
86 Correct 31 ms 8568 KB n=2000
87 Correct 32 ms 8552 KB n=2000
88 Correct 29 ms 8568 KB n=2000
89 Correct 27 ms 8568 KB n=2000
90 Correct 28 ms 8568 KB n=2000
91 Correct 16 ms 8568 KB n=2000

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4984 KB n=5
2 Correct 5 ms 5112 KB n=100
3 Correct 5 ms 5112 KB n=100
4 Correct 6 ms 5116 KB n=100
5 Correct 6 ms 5112 KB n=100
6 Correct 6 ms 5240 KB n=100
7 Correct 6 ms 5112 KB n=100
8 Correct 6 ms 5212 KB n=100
9 Correct 6 ms 5112 KB n=100
10 Correct 6 ms 5228 KB n=100
11 Correct 6 ms 5112 KB n=100
12 Correct 6 ms 5112 KB n=100
13 Correct 6 ms 5112 KB n=100
14 Correct 6 ms 5112 KB n=100
15 Correct 6 ms 5112 KB n=100
16 Correct 5 ms 5112 KB n=100
17 Correct 6 ms 5240 KB n=100
18 Correct 6 ms 5240 KB n=100
19 Correct 6 ms 5112 KB n=100
20 Correct 6 ms 5112 KB n=100
21 Correct 6 ms 5112 KB n=100
22 Correct 6 ms 5112 KB n=100
23 Correct 6 ms 5112 KB n=100
24 Correct 6 ms 5112 KB n=100
25 Correct 6 ms 5112 KB n=100
26 Correct 6 ms 5112 KB n=12
27 Correct 6 ms 5112 KB n=100
28 Correct 10 ms 5756 KB n=500
29 Correct 9 ms 5880 KB n=500
30 Correct 9 ms 5880 KB n=500
31 Correct 9 ms 5752 KB n=500
32 Correct 8 ms 5752 KB n=500
33 Correct 10 ms 5752 KB n=500
34 Correct 8 ms 5752 KB n=500
35 Correct 9 ms 5756 KB n=500
36 Correct 7 ms 5880 KB n=500
37 Correct 7 ms 5752 KB n=500
38 Correct 7 ms 5880 KB n=500
39 Correct 7 ms 5752 KB n=500
40 Correct 8 ms 5752 KB n=500
41 Correct 7 ms 5880 KB n=500
42 Correct 9 ms 5880 KB n=500
43 Correct 10 ms 5852 KB n=500
44 Correct 10 ms 5752 KB n=500
45 Correct 10 ms 5880 KB n=500
46 Correct 9 ms 5880 KB n=500
47 Correct 10 ms 5752 KB n=500
48 Correct 9 ms 5752 KB n=500
49 Correct 10 ms 5880 KB n=500
50 Correct 10 ms 5752 KB n=500
51 Correct 10 ms 5880 KB n=500
52 Correct 10 ms 5880 KB n=500
53 Correct 10 ms 5880 KB n=500
54 Correct 9 ms 5880 KB n=500
55 Correct 7 ms 5752 KB n=278
56 Correct 10 ms 5880 KB n=500
57 Correct 10 ms 5752 KB n=500
58 Correct 8 ms 5880 KB n=500
59 Correct 27 ms 8440 KB n=2000
60 Correct 31 ms 8568 KB n=2000
61 Correct 38 ms 8568 KB n=2000
62 Correct 32 ms 8568 KB n=2000
63 Correct 30 ms 8572 KB n=2000
64 Correct 31 ms 8548 KB n=2000
65 Correct 29 ms 8500 KB n=2000
66 Correct 32 ms 8696 KB n=2000
67 Correct 31 ms 8568 KB n=2000
68 Correct 29 ms 8568 KB n=2000
69 Correct 17 ms 8568 KB n=2000
70 Correct 16 ms 8568 KB n=2000
71 Correct 17 ms 8568 KB n=2000
72 Correct 20 ms 8568 KB n=2000
73 Correct 19 ms 8564 KB n=2000
74 Correct 25 ms 8440 KB n=1844
75 Correct 19 ms 8568 KB n=2000
76 Correct 29 ms 8568 KB n=2000
77 Correct 28 ms 8568 KB n=2000
78 Correct 28 ms 8568 KB n=2000
79 Correct 27 ms 8492 KB n=2000
80 Correct 30 ms 8568 KB n=2000
81 Correct 31 ms 8568 KB n=2000
82 Correct 28 ms 8440 KB n=2000
83 Correct 32 ms 8568 KB n=2000
84 Correct 28 ms 8568 KB n=2000
85 Correct 33 ms 8696 KB n=2000
86 Correct 31 ms 8568 KB n=2000
87 Correct 32 ms 8552 KB n=2000
88 Correct 29 ms 8568 KB n=2000
89 Correct 27 ms 8568 KB n=2000
90 Correct 28 ms 8568 KB n=2000
91 Correct 16 ms 8568 KB n=2000
92 Runtime error 913 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
93 Halted 0 ms 0 KB -