oj.uz

Submission #44021

# Submission time Handle Problem Language Result Execution time Memory
44021 2018-03-29T10:56:44 Z Nordway Birthday gift (IZhO18_treearray) C++14
100 / 100
 2124 ms 262144 KB 
#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <cstring>
#include <climits>
#include <string.h>
#include <stdio.h>
#include <assert.h>

#define x first
#define y second
#define pb push_back
#define mp make_pair
#define low_b lower_bound
#define up_b upper_bound
#define all(v) v.begin(), v.end()

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef set<int> si;

const int N = 2 * 1e+5 + 111;
const int mxn = 1e+6 + 111;

vi g[mxn];
int a[mxn], lvl[mxn], up[mxn][18], d[mxn];
si cnt[N], L[N];

inline void dfs(int v, int p){
    lvl[v] = lvl[p] + 1;
    up[v][0] = p;
    for(int i = 1; i <= 17; i++){
        up[v][i] = up[up[v][i - 1]][i - 1];
    }
    d[v] = 1;
    for(auto to : g[v]){
        if(to == p)continue;
        dfs(to, v);
        d[v] += d[to];
    }
}

inline int lca(int x, int y){
    if(lvl[x] > lvl[y]) swap(x, y);
    for(int i = 17; i >= 0; i--){
        if(lvl[up[y][i]] >= lvl[x])y = up[y][i];
    }
    if(x == y)return x;
    for(int i = 17; i >= 0; i--){
        if(up[y][i] != up[x][i]){
            x = up[x][i];
            y = up[y][i];
        }
    }
    return up[x][0];
}

int main(){
    ios_base :: sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n, m, q;
    cin >> n >> m >> q;
    for(int i = 1; i < n; i++){
        int u, v;
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }
    dfs(1, 0);
    for(int i = 1; i <= m; i++){
        cin >> a[i];
        cnt[a[i]].insert(i);
        if(i != 1){
            L[lca(a[i], a[i - 1])].insert(i - 1);
        }
    }
    while(q--){
        int type;
        cin >> type;
        if(type == 1){
            int pos, v;
            cin >> pos >> v;
            cnt[a[pos]].erase(pos);
            if(pos != 1){
                L[lca(a[pos], a[pos - 1])].erase(pos - 1);
            }
            if(pos != n){
                L[lca(a[pos], a[pos + 1])].erase(pos);
            }
            a[pos] = v;
            cnt[v].insert(pos);
            if(pos != 1){
                L[lca(a[pos - 1], a[pos])].insert(pos - 1);
            }
            if(pos != n){
                L[lca(a[pos], a[pos + 1])].insert(pos);
            }
        }
        else{
            int l, r, v;
            cin >> l >> r >> v;
            if(!cnt[v].empty()){
                auto i = cnt[v].low_b(l);
                if(i != cnt[v].end()){
                    int ans = *i;
                    if(ans <= r){
                        cout << ans << " " << ans << endl;
                        continue;
                    }
                }
            }
            if (!L[v].empty()) {
				auto i = L[v].lower_bound(l);
				if (i != L[v].end()) {
					int ans = *i;
					if (ans + 1 <= r) {
						cout << ans << " " << ans + 1 << endl;
				    	continue;
					}
				}
			}
			cout << "-1 -1" << endl;
        }
    }
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 42616 KB n=5
2 Correct 37 ms 42724 KB n=100
3 Correct 38 ms 42724 KB n=100
4 Correct 37 ms 42724 KB n=100
5 Correct 45 ms 42748 KB n=100
6 Correct 37 ms 42828 KB n=100
7 Correct 42 ms 42828 KB n=100
8 Correct 41 ms 42828 KB n=100
9 Correct 41 ms 42828 KB n=100
10 Correct 37 ms 42912 KB n=100
11 Correct 38 ms 42912 KB n=100
12 Correct 38 ms 42916 KB n=100
13 Correct 40 ms 42916 KB n=100
14 Correct 39 ms 42916 KB n=100
15 Correct 39 ms 42916 KB n=100
16 Correct 37 ms 42916 KB n=100
17 Correct 37 ms 42916 KB n=100
18 Correct 37 ms 42916 KB n=100
19 Correct 45 ms 42916 KB n=100
20 Correct 38 ms 42916 KB n=100
21 Correct 39 ms 42916 KB n=100
22 Correct 39 ms 42916 KB n=100
23 Correct 42 ms 42916 KB n=100
24 Correct 40 ms 42916 KB n=100
25 Correct 46 ms 42916 KB n=100
26 Correct 47 ms 42916 KB n=12
27 Correct 39 ms 42916 KB n=100

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 42616 KB n=5
2 Correct 37 ms 42724 KB n=100
3 Correct 38 ms 42724 KB n=100
4 Correct 37 ms 42724 KB n=100
5 Correct 45 ms 42748 KB n=100
6 Correct 37 ms 42828 KB n=100
7 Correct 42 ms 42828 KB n=100
8 Correct 41 ms 42828 KB n=100
9 Correct 41 ms 42828 KB n=100
10 Correct 37 ms 42912 KB n=100
11 Correct 38 ms 42912 KB n=100
12 Correct 38 ms 42916 KB n=100
13 Correct 40 ms 42916 KB n=100
14 Correct 39 ms 42916 KB n=100
15 Correct 39 ms 42916 KB n=100
16 Correct 37 ms 42916 KB n=100
17 Correct 37 ms 42916 KB n=100
18 Correct 37 ms 42916 KB n=100
19 Correct 45 ms 42916 KB n=100
20 Correct 38 ms 42916 KB n=100
21 Correct 39 ms 42916 KB n=100
22 Correct 39 ms 42916 KB n=100
23 Correct 42 ms 42916 KB n=100
24 Correct 40 ms 42916 KB n=100
25 Correct 46 ms 42916 KB n=100
26 Correct 47 ms 42916 KB n=12
27 Correct 39 ms 42916 KB n=100
28 Correct 41 ms 42952 KB n=500
29 Correct 38 ms 42980 KB n=500
30 Correct 38 ms 42980 KB n=500
31 Correct 38 ms 42980 KB n=500
32 Correct 42 ms 42980 KB n=500
33 Correct 38 ms 43036 KB n=500
34 Correct 38 ms 43036 KB n=500
35 Correct 38 ms 43036 KB n=500
36 Correct 42 ms 43036 KB n=500
37 Correct 41 ms 43036 KB n=500
38 Correct 38 ms 43036 KB n=500
39 Correct 38 ms 43036 KB n=500
40 Correct 37 ms 43036 KB n=500
41 Correct 39 ms 43036 KB n=500
42 Correct 39 ms 43036 KB n=500
43 Correct 39 ms 43036 KB n=500
44 Correct 39 ms 43036 KB n=500
45 Correct 39 ms 43036 KB n=500
46 Correct 39 ms 43036 KB n=500
47 Correct 39 ms 43036 KB n=500
48 Correct 39 ms 43036 KB n=500
49 Correct 39 ms 43036 KB n=500
50 Correct 37 ms 43036 KB n=500
51 Correct 37 ms 43036 KB n=500
52 Correct 38 ms 43036 KB n=500
53 Correct 37 ms 43036 KB n=500
54 Correct 44 ms 43036 KB n=500
55 Correct 39 ms 43036 KB n=278
56 Correct 39 ms 43056 KB n=500
57 Correct 41 ms 43056 KB n=500
58 Correct 38 ms 43056 KB n=500

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 42616 KB n=5
2 Correct 37 ms 42724 KB n=100
3 Correct 38 ms 42724 KB n=100
4 Correct 37 ms 42724 KB n=100
5 Correct 45 ms 42748 KB n=100
6 Correct 37 ms 42828 KB n=100
7 Correct 42 ms 42828 KB n=100
8 Correct 41 ms 42828 KB n=100
9 Correct 41 ms 42828 KB n=100
10 Correct 37 ms 42912 KB n=100
11 Correct 38 ms 42912 KB n=100
12 Correct 38 ms 42916 KB n=100
13 Correct 40 ms 42916 KB n=100
14 Correct 39 ms 42916 KB n=100
15 Correct 39 ms 42916 KB n=100
16 Correct 37 ms 42916 KB n=100
17 Correct 37 ms 42916 KB n=100
18 Correct 37 ms 42916 KB n=100
19 Correct 45 ms 42916 KB n=100
20 Correct 38 ms 42916 KB n=100
21 Correct 39 ms 42916 KB n=100
22 Correct 39 ms 42916 KB n=100
23 Correct 42 ms 42916 KB n=100
24 Correct 40 ms 42916 KB n=100
25 Correct 46 ms 42916 KB n=100
26 Correct 47 ms 42916 KB n=12
27 Correct 39 ms 42916 KB n=100
28 Correct 41 ms 42952 KB n=500
29 Correct 38 ms 42980 KB n=500
30 Correct 38 ms 42980 KB n=500
31 Correct 38 ms 42980 KB n=500
32 Correct 42 ms 42980 KB n=500
33 Correct 38 ms 43036 KB n=500
34 Correct 38 ms 43036 KB n=500
35 Correct 38 ms 43036 KB n=500
36 Correct 42 ms 43036 KB n=500
37 Correct 41 ms 43036 KB n=500
38 Correct 38 ms 43036 KB n=500
39 Correct 38 ms 43036 KB n=500
40 Correct 37 ms 43036 KB n=500
41 Correct 39 ms 43036 KB n=500
42 Correct 39 ms 43036 KB n=500
43 Correct 39 ms 43036 KB n=500
44 Correct 39 ms 43036 KB n=500
45 Correct 39 ms 43036 KB n=500
46 Correct 39 ms 43036 KB n=500
47 Correct 39 ms 43036 KB n=500
48 Correct 39 ms 43036 KB n=500
49 Correct 39 ms 43036 KB n=500
50 Correct 37 ms 43036 KB n=500
51 Correct 37 ms 43036 KB n=500
52 Correct 38 ms 43036 KB n=500
53 Correct 37 ms 43036 KB n=500
54 Correct 44 ms 43036 KB n=500
55 Correct 39 ms 43036 KB n=278
56 Correct 39 ms 43056 KB n=500
57 Correct 41 ms 43056 KB n=500
58 Correct 38 ms 43056 KB n=500
59 Correct 45 ms 43296 KB n=2000
60 Correct 43 ms 43392 KB n=2000
61 Correct 46 ms 43392 KB n=2000
62 Correct 44 ms 43392 KB n=2000
63 Correct 45 ms 43404 KB n=2000
64 Correct 52 ms 43404 KB n=2000
65 Correct 44 ms 43404 KB n=2000
66 Correct 44 ms 43420 KB n=2000
67 Correct 46 ms 43420 KB n=2000
68 Correct 43 ms 43436 KB n=2000
69 Correct 43 ms 43436 KB n=2000
70 Correct 45 ms 43436 KB n=2000
71 Correct 43 ms 43436 KB n=2000
72 Correct 44 ms 43436 KB n=2000
73 Correct 49 ms 43436 KB n=2000
74 Correct 42 ms 43436 KB n=1844
75 Correct 43 ms 43436 KB n=2000
76 Correct 45 ms 43436 KB n=2000
77 Correct 44 ms 43436 KB n=2000
78 Correct 55 ms 43436 KB n=2000
79 Correct 44 ms 43436 KB n=2000
80 Correct 44 ms 43436 KB n=2000
81 Correct 44 ms 43436 KB n=2000
82 Correct 44 ms 43436 KB n=2000
83 Correct 42 ms 43440 KB n=2000
84 Correct 43 ms 43440 KB n=2000
85 Correct 44 ms 43440 KB n=2000
86 Correct 44 ms 43440 KB n=2000
87 Correct 44 ms 43440 KB n=2000
88 Correct 46 ms 43440 KB n=2000
89 Correct 43 ms 43568 KB n=2000
90 Correct 48 ms 43652 KB n=2000
91 Correct 44 ms 43652 KB n=2000

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 42616 KB n=5
2 Correct 37 ms 42724 KB n=100
3 Correct 38 ms 42724 KB n=100
4 Correct 37 ms 42724 KB n=100
5 Correct 45 ms 42748 KB n=100
6 Correct 37 ms 42828 KB n=100
7 Correct 42 ms 42828 KB n=100
8 Correct 41 ms 42828 KB n=100
9 Correct 41 ms 42828 KB n=100
10 Correct 37 ms 42912 KB n=100
11 Correct 38 ms 42912 KB n=100
12 Correct 38 ms 42916 KB n=100
13 Correct 40 ms 42916 KB n=100
14 Correct 39 ms 42916 KB n=100
15 Correct 39 ms 42916 KB n=100
16 Correct 37 ms 42916 KB n=100
17 Correct 37 ms 42916 KB n=100
18 Correct 37 ms 42916 KB n=100
19 Correct 45 ms 42916 KB n=100
20 Correct 38 ms 42916 KB n=100
21 Correct 39 ms 42916 KB n=100
22 Correct 39 ms 42916 KB n=100
23 Correct 42 ms 42916 KB n=100
24 Correct 40 ms 42916 KB n=100
25 Correct 46 ms 42916 KB n=100
26 Correct 47 ms 42916 KB n=12
27 Correct 39 ms 42916 KB n=100
28 Correct 41 ms 42952 KB n=500
29 Correct 38 ms 42980 KB n=500
30 Correct 38 ms 42980 KB n=500
31 Correct 38 ms 42980 KB n=500
32 Correct 42 ms 42980 KB n=500
33 Correct 38 ms 43036 KB n=500
34 Correct 38 ms 43036 KB n=500
35 Correct 38 ms 43036 KB n=500
36 Correct 42 ms 43036 KB n=500
37 Correct 41 ms 43036 KB n=500
38 Correct 38 ms 43036 KB n=500
39 Correct 38 ms 43036 KB n=500
40 Correct 37 ms 43036 KB n=500
41 Correct 39 ms 43036 KB n=500
42 Correct 39 ms 43036 KB n=500
43 Correct 39 ms 43036 KB n=500
44 Correct 39 ms 43036 KB n=500
45 Correct 39 ms 43036 KB n=500
46 Correct 39 ms 43036 KB n=500
47 Correct 39 ms 43036 KB n=500
48 Correct 39 ms 43036 KB n=500
49 Correct 39 ms 43036 KB n=500
50 Correct 37 ms 43036 KB n=500
51 Correct 37 ms 43036 KB n=500
52 Correct 38 ms 43036 KB n=500
53 Correct 37 ms 43036 KB n=500
54 Correct 44 ms 43036 KB n=500
55 Correct 39 ms 43036 KB n=278
56 Correct 39 ms 43056 KB n=500
57 Correct 41 ms 43056 KB n=500
58 Correct 38 ms 43056 KB n=500
59 Correct 45 ms 43296 KB n=2000
60 Correct 43 ms 43392 KB n=2000
61 Correct 46 ms 43392 KB n=2000
62 Correct 44 ms 43392 KB n=2000
63 Correct 45 ms 43404 KB n=2000
64 Correct 52 ms 43404 KB n=2000
65 Correct 44 ms 43404 KB n=2000
66 Correct 44 ms 43420 KB n=2000
67 Correct 46 ms 43420 KB n=2000
68 Correct 43 ms 43436 KB n=2000
69 Correct 43 ms 43436 KB n=2000
70 Correct 45 ms 43436 KB n=2000
71 Correct 43 ms 43436 KB n=2000
72 Correct 44 ms 43436 KB n=2000
73 Correct 49 ms 43436 KB n=2000
74 Correct 42 ms 43436 KB n=1844
75 Correct 43 ms 43436 KB n=2000
76 Correct 45 ms 43436 KB n=2000
77 Correct 44 ms 43436 KB n=2000
78 Correct 55 ms 43436 KB n=2000
79 Correct 44 ms 43436 KB n=2000
80 Correct 44 ms 43436 KB n=2000
81 Correct 44 ms 43436 KB n=2000
82 Correct 44 ms 43436 KB n=2000
83 Correct 42 ms 43440 KB n=2000
84 Correct 43 ms 43440 KB n=2000
85 Correct 44 ms 43440 KB n=2000
86 Correct 44 ms 43440 KB n=2000
87 Correct 44 ms 43440 KB n=2000
88 Correct 46 ms 43440 KB n=2000
89 Correct 43 ms 43568 KB n=2000
90 Correct 48 ms 43652 KB n=2000
91 Correct 44 ms 43652 KB n=2000
92 Correct 1261 ms 93220 KB n=200000
93 Correct 2008 ms 102932 KB n=200000
94 Correct 1945 ms 112848 KB n=200000
95 Correct 1283 ms 114796 KB n=200000
96 Correct 1313 ms 121348 KB n=200000
97 Correct 1950 ms 130580 KB n=200000
98 Correct 1300 ms 135460 KB n=200000
99 Correct 1583 ms 142112 KB n=200000
100 Correct 1279 ms 149056 KB n=200000
101 Correct 1763 ms 162172 KB n=200000
102 Correct 928 ms 164528 KB n=200000
103 Correct 970 ms 171132 KB n=200000
104 Correct 973 ms 177724 KB n=200000
105 Correct 961 ms 184972 KB n=200000
106 Correct 1035 ms 192284 KB n=200000
107 Correct 974 ms 199608 KB n=200000
108 Correct 1532 ms 205476 KB n=200000
109 Correct 1362 ms 212364 KB n=200000
110 Correct 1375 ms 219188 KB n=200000
111 Correct 1248 ms 225544 KB n=200000
112 Correct 1684 ms 237936 KB n=200000
113 Correct 1988 ms 242604 KB n=200000
114 Correct 1338 ms 247004 KB n=200000
115 Correct 1963 ms 254932 KB n=200000
116 Correct 1247 ms 261444 KB n=200000
117 Correct 1883 ms 262144 KB n=200000
118 Correct 2124 ms 262144 KB n=200000
119 Correct 1252 ms 262144 KB n=200000
120 Correct 1976 ms 262144 KB n=200000
121 Correct 1831 ms 262144 KB n=200000
122 Correct 1780 ms 262144 KB n=200000
123 Correct 994 ms 262144 KB n=200000
124 Correct 455 ms 262144 KB n=25264