oj.uz

Submission #90868

# Submission time Handle Problem Language Result Execution time Memory
90868 2018-12-25T03:52:44 Z adlet Birthday gift (IZhO18_treearray) C++17
12 / 100
 4000 ms 5536 KB 
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)

using namespace std;

typedef long long ll;

const int N = 2e5 + 5;
const int mod = 1e9 + 7;
const double PI = acos(-1.0);
const int lg = log2(500) + 1;

int n, m, q, timer, t[N * 4], x[N], lvl[N], tin[N], tout[N], used[N], up[N][lg + 5];

vector < int > g[N];

int dfs(int v, int p = 1, int h = 0) {
    used[v] = 1;
    up[v][0] = p;
    tin[v] = ++timer;
    lvl[v] = h;
    for (int i = 1; i <= lg; ++i) {
        up[v][i] = up[up[v][i - 1]][i - 1];
    }
    for (int to : g[v]) {
        if (!used[to]) {
            dfs(to, v, h + 1);
        }
    }
    tout[v] = ++timer;
}

int lca(int a, int b) {
    if (lvl[a] < lvl[b])
        swap(a, b);
    if (tin[b] <= tin[a] && tout[b] >= tout[a])
        return b;
    for (int i = lg; i >= 0; --i) {
        if (lvl[up[a][i]] >= lvl[b]) {
            a = up[a][i];
        }
    }
    if (a == b)
        return a;
    for (int i = lg; i >= 0; --i) {
        if (up[a][i] != up[b][i]) {
            a = up[a][i];
            b = up[b][i];
        }
    }
    return up[a][0];
}

inline void build(int v, int tl, int tr) {
    if (tl == tr) {
        t[v] = x[tl];
        return;
    }
    int tm = tl + tr >> 1;
    build(v + v, tl, tm);
    build(v + v + 1, tm + 1, tr);
    t[v] = lca(t[v + v], t[v + v + 1]);
}

inline void upd(int v, int tl, int tr, int pos, int x) {
    if (tl == tr) {
        t[v] = x;
        return;
    }
    int tm = tl + tr >> 1;
    if (pos <= tm)
        upd(v + v, tl, tm, pos, x);
    else
        upd(v + v + 1, tm + 1, tr, pos, x);
    t[v] = lca(t[v + v], t[v + v + 1]);
}

int get(int v, int tl, int tr, int l, int r) {
    if (tl > r || tr < l)
        return -1;
    if (tl >= l && tr <= r)
        return t[v];
    int tm = tl + tr >> 1;
    int lv = get(v + v, tl, tm, l, r);
    int rv = get(v + v + 1, tm + 1, tr, l, r);
    if (lv == -1)
        lv = rv;
    else if (rv == -1)
        rv = lv;
    return lca(lv, rv);
}

int getq(int l, int r) {
    return get(1, 1, m, l, r);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> q;
    for (int i = 1; i < n; ++i) {
        int v, u;
        cin >> v >> u;
        g[v].push_back(u);
        g[u].push_back(v);
    }
    dfs(1);
    for (int i = 1; i <= m; ++i) {
        cin >> x[i];
    }
    build(1, 1, m);
    while (q--) {
        int ll = -1, rr = -1, l, r, type;
        cin >> type >> l >> r;
        if (type == 1) {
            upd(1, 1, m, l, r);
        } else {
            int v;
            cin >> v;
            for (int a = l; a <= r; ++a) {
                for (int b = a; b <= r; ++b) {
                    if (getq(a, b) == v) {
                        ll = a;
                        rr = b;
                        break;
                    }
                }
                if (max(ll, rr) != -1)
                    break;
            }
            cout << ll << " " << rr << "\n";
        }
    }
}
/*
5 4 4
1 2
3 1
3 4
5 3
4 5 2 3
2 1 3 1
1 3 5
2 3 4 5
2 1 3 1


*/

Compilation message

treearray.cpp: In function 'int dfs(int, int, int)':
treearray.cpp:33:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
treearray.cpp: In function 'void build(int, int, int)':
treearray.cpp:61:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int tm = tl + tr >> 1;
              ~~~^~~~
treearray.cpp: In function 'void upd(int, int, int, int, int)':
treearray.cpp:72:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int tm = tl + tr >> 1;
              ~~~^~~~
treearray.cpp: In function 'int get(int, int, int, int, int)':
treearray.cpp:85:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int tm = tl + tr >> 1;
              ~~~^~~~

Subtask #1
12.0 / 12.0

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

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB n=5
2 Correct 11 ms 5196 KB n=100
3 Correct 9 ms 5196 KB n=100
4 Correct 8 ms 5196 KB n=100
5 Correct 7 ms 5196 KB n=100
6 Correct 45 ms 5356 KB n=100
7 Correct 45 ms 5356 KB n=100
8 Correct 10 ms 5356 KB n=100
9 Correct 11 ms 5356 KB n=100
10 Correct 26 ms 5356 KB n=100
11 Correct 27 ms 5356 KB n=100
12 Correct 6 ms 5356 KB n=100
13 Correct 6 ms 5356 KB n=100
14 Correct 6 ms 5356 KB n=100
15 Correct 6 ms 5356 KB n=100
16 Correct 7 ms 5356 KB n=100
17 Correct 11 ms 5488 KB n=100
18 Correct 9 ms 5488 KB n=100
19 Correct 6 ms 5488 KB n=100
20 Correct 9 ms 5488 KB n=100
21 Correct 9 ms 5488 KB n=100
22 Correct 6 ms 5488 KB n=100
23 Correct 15 ms 5488 KB n=100
24 Correct 15 ms 5488 KB n=100
25 Correct 7 ms 5488 KB n=100
26 Correct 6 ms 5488 KB n=12
27 Correct 21 ms 5488 KB n=100
28 Correct 14 ms 5488 KB n=500
29 Correct 526 ms 5488 KB n=500
30 Correct 379 ms 5488 KB n=500
31 Correct 445 ms 5488 KB n=500
32 Correct 23 ms 5488 KB n=500
33 Correct 365 ms 5488 KB n=500
34 Correct 7 ms 5488 KB n=500
35 Correct 449 ms 5536 KB n=500
36 Execution timed out 4030 ms 5536 KB Time limit exceeded
37 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB n=5
2 Correct 11 ms 5196 KB n=100
3 Correct 9 ms 5196 KB n=100
4 Correct 8 ms 5196 KB n=100
5 Correct 7 ms 5196 KB n=100
6 Correct 45 ms 5356 KB n=100
7 Correct 45 ms 5356 KB n=100
8 Correct 10 ms 5356 KB n=100
9 Correct 11 ms 5356 KB n=100
10 Correct 26 ms 5356 KB n=100
11 Correct 27 ms 5356 KB n=100
12 Correct 6 ms 5356 KB n=100
13 Correct 6 ms 5356 KB n=100
14 Correct 6 ms 5356 KB n=100
15 Correct 6 ms 5356 KB n=100
16 Correct 7 ms 5356 KB n=100
17 Correct 11 ms 5488 KB n=100
18 Correct 9 ms 5488 KB n=100
19 Correct 6 ms 5488 KB n=100
20 Correct 9 ms 5488 KB n=100
21 Correct 9 ms 5488 KB n=100
22 Correct 6 ms 5488 KB n=100
23 Correct 15 ms 5488 KB n=100
24 Correct 15 ms 5488 KB n=100
25 Correct 7 ms 5488 KB n=100
26 Correct 6 ms 5488 KB n=12
27 Correct 21 ms 5488 KB n=100
28 Correct 14 ms 5488 KB n=500
29 Correct 526 ms 5488 KB n=500
30 Correct 379 ms 5488 KB n=500
31 Correct 445 ms 5488 KB n=500
32 Correct 23 ms 5488 KB n=500
33 Correct 365 ms 5488 KB n=500
34 Correct 7 ms 5488 KB n=500
35 Correct 449 ms 5536 KB n=500
36 Execution timed out 4030 ms 5536 KB Time limit exceeded
37 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB n=5
2 Correct 11 ms 5196 KB n=100
3 Correct 9 ms 5196 KB n=100
4 Correct 8 ms 5196 KB n=100
5 Correct 7 ms 5196 KB n=100
6 Correct 45 ms 5356 KB n=100
7 Correct 45 ms 5356 KB n=100
8 Correct 10 ms 5356 KB n=100
9 Correct 11 ms 5356 KB n=100
10 Correct 26 ms 5356 KB n=100
11 Correct 27 ms 5356 KB n=100
12 Correct 6 ms 5356 KB n=100
13 Correct 6 ms 5356 KB n=100
14 Correct 6 ms 5356 KB n=100
15 Correct 6 ms 5356 KB n=100
16 Correct 7 ms 5356 KB n=100
17 Correct 11 ms 5488 KB n=100
18 Correct 9 ms 5488 KB n=100
19 Correct 6 ms 5488 KB n=100
20 Correct 9 ms 5488 KB n=100
21 Correct 9 ms 5488 KB n=100
22 Correct 6 ms 5488 KB n=100
23 Correct 15 ms 5488 KB n=100
24 Correct 15 ms 5488 KB n=100
25 Correct 7 ms 5488 KB n=100
26 Correct 6 ms 5488 KB n=12
27 Correct 21 ms 5488 KB n=100
28 Correct 14 ms 5488 KB n=500
29 Correct 526 ms 5488 KB n=500
30 Correct 379 ms 5488 KB n=500
31 Correct 445 ms 5488 KB n=500
32 Correct 23 ms 5488 KB n=500
33 Correct 365 ms 5488 KB n=500
34 Correct 7 ms 5488 KB n=500
35 Correct 449 ms 5536 KB n=500
36 Execution timed out 4030 ms 5536 KB Time limit exceeded
37 Halted 0 ms 0 KB -