oj.uz

Submission #158108

# Submission time Handle Problem Language Result Execution time Memory
158108 2019-10-14T18:59:06 Z brcode Birthday gift (IZhO18_treearray) C++14
100 / 100
 2353 ms 88744 KB 
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5+5;
int dp[MAXN][25];
int depth[MAXN];
int seq[MAXN];
int holdlca[MAXN];
vector<int> v1[MAXN];
set<int> v2[MAXN];
set<int> v3[MAXN];
void dfs(int curr,int par,int dep){
    dp[curr][0] = par;
    depth[curr] = dep;
    for(int x:v1[curr]){
        if(x!=par){

            dfs(x,curr,dep+1);
        }
    }
}
int lca(int a,int b){
    if(depth[a]<depth[b]){
        swap(a,b);
    }
    for(int j=20;j>=0;j--){
        if(dp[a][j]!=-1 && depth[dp[a][j]]>=depth[b]){
            a = dp[a][j];
        }

    }
    if(a==b){
        return a;
    }
    for(int i=20;i>=0;i--){
        if(dp[a][i]!=-1 && dp[a][i]!=dp[b][i]){
            a = dp[a][i];
            b = dp[b][i];
        }
    }
    return dp[a][0];
}
int main(){
    int n,m,q;
    cin>>n>>m>>q;
    for(int i=1;i<n;i++){
        int x,y;
        cin>>x>>y;
        v1[x].push_back(y);
        v1[y].push_back(x);
    }
    for(int i=1;i<=m;i++){
        cin>>seq[i];
        v3[seq[i]].insert(i);
    }
    dfs(1,-1,1);
    for(int j=1;j<=20;j++){
        for(int i=1;i<=n;i++){
            if(dp[i][j-1]==-1){
                dp[i][j] = -1;
            }else{
                dp[i][j] = dp[dp[i][j-1]][j-1];
            }
        }
    }
    //cout<<123<<endl;cout
    for(int j=1;j<m;j++){
        holdlca[j] = lca(seq[j],seq[j+1]);
        v2[holdlca[j]].insert(j);
        
    }

    
    while(q--){
        int t;
        cin>>t;
      
            if(t==1){
                int pos,v;
                cin>>pos>>v;
                v3[seq[pos]].erase(pos);
                seq[pos] = v;
                v3[seq[pos]].insert(pos);
                if(pos<m){
                    int temp = holdlca[pos];
                    v2[temp].erase(pos);
                    holdlca[pos] = lca(seq[pos],seq[pos+1]);
                    v2[holdlca[pos]].insert(pos);
                }
                
                
                if(pos>1){
                    int temp  = holdlca[pos-1];
                    v2[temp].erase(pos-1);
                    holdlca[pos-1] = lca(seq[pos-1],seq[pos]);
                    v2[holdlca[pos-1]].insert(pos-1);
                    
                
                }
                
            }else{
                int l,r,v;
                cin>>l>>r>>v;
                //cout<<123<<" "<<v<<" "<<v2[v].size()<<endl;
                
                auto hold2= v3[v].lower_bound(l);
                int ans1 = -1;
                int ans2= -1;
                if(hold2!=v3[v].end() && (*hold2)<=r){
                    ans1 = (*hold2);
                    ans2= (*hold2);
                    
                }else{
                    auto hold =v2[v].lower_bound(l);
                    if(hold!=v2[v].end() && (*hold)<r){
                        ans1 = (*hold);
                        ans2=  (*hold)+1;
                    }
                }
                cout<<ans1<<" "<<ans2<<endl;
            }
    }
    
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23800 KB n=5
2 Correct 24 ms 23800 KB n=100
3 Correct 23 ms 23928 KB n=100
4 Correct 23 ms 23800 KB n=100
5 Correct 23 ms 23800 KB n=100
6 Correct 28 ms 23928 KB n=100
7 Correct 28 ms 23800 KB n=100
8 Correct 24 ms 23928 KB n=100
9 Correct 23 ms 23928 KB n=100
10 Correct 23 ms 23800 KB n=100
11 Correct 23 ms 23800 KB n=100
12 Correct 23 ms 23800 KB n=100
13 Correct 24 ms 23800 KB n=100
14 Correct 24 ms 23800 KB n=100
15 Correct 28 ms 23804 KB n=100
16 Correct 28 ms 23860 KB n=100
17 Correct 29 ms 23800 KB n=100
18 Correct 24 ms 23800 KB n=100
19 Correct 26 ms 23928 KB n=100
20 Correct 24 ms 23800 KB n=100
21 Correct 27 ms 23928 KB n=100
22 Correct 28 ms 23996 KB n=100
23 Correct 31 ms 23800 KB n=100
24 Correct 26 ms 23884 KB n=100
25 Correct 24 ms 23800 KB n=100
26 Correct 29 ms 23800 KB n=12
27 Correct 28 ms 23796 KB n=100

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23800 KB n=5
2 Correct 24 ms 23800 KB n=100
3 Correct 23 ms 23928 KB n=100
4 Correct 23 ms 23800 KB n=100
5 Correct 23 ms 23800 KB n=100
6 Correct 28 ms 23928 KB n=100
7 Correct 28 ms 23800 KB n=100
8 Correct 24 ms 23928 KB n=100
9 Correct 23 ms 23928 KB n=100
10 Correct 23 ms 23800 KB n=100
11 Correct 23 ms 23800 KB n=100
12 Correct 23 ms 23800 KB n=100
13 Correct 24 ms 23800 KB n=100
14 Correct 24 ms 23800 KB n=100
15 Correct 28 ms 23804 KB n=100
16 Correct 28 ms 23860 KB n=100
17 Correct 29 ms 23800 KB n=100
18 Correct 24 ms 23800 KB n=100
19 Correct 26 ms 23928 KB n=100
20 Correct 24 ms 23800 KB n=100
21 Correct 27 ms 23928 KB n=100
22 Correct 28 ms 23996 KB n=100
23 Correct 31 ms 23800 KB n=100
24 Correct 26 ms 23884 KB n=100
25 Correct 24 ms 23800 KB n=100
26 Correct 29 ms 23800 KB n=12
27 Correct 28 ms 23796 KB n=100
28 Correct 31 ms 23928 KB n=500
29 Correct 31 ms 23936 KB n=500
30 Correct 26 ms 23960 KB n=500
31 Correct 34 ms 23928 KB n=500
32 Correct 26 ms 23928 KB n=500
33 Correct 25 ms 23928 KB n=500
34 Correct 30 ms 23928 KB n=500
35 Correct 27 ms 23928 KB n=500
36 Correct 29 ms 23960 KB n=500
37 Correct 31 ms 23928 KB n=500
38 Correct 26 ms 23928 KB n=500
39 Correct 29 ms 24056 KB n=500
40 Correct 32 ms 23928 KB n=500
41 Correct 31 ms 23928 KB n=500
42 Correct 30 ms 23928 KB n=500
43 Correct 31 ms 24000 KB n=500
44 Correct 26 ms 23928 KB n=500
45 Correct 30 ms 23980 KB n=500
46 Correct 26 ms 23928 KB n=500
47 Correct 28 ms 24028 KB n=500
48 Correct 27 ms 23928 KB n=500
49 Correct 26 ms 24056 KB n=500
50 Correct 30 ms 23932 KB n=500
51 Correct 26 ms 23928 KB n=500
52 Correct 26 ms 23928 KB n=500
53 Correct 31 ms 23944 KB n=500
54 Correct 26 ms 23928 KB n=500
55 Correct 24 ms 23928 KB n=278
56 Correct 26 ms 23932 KB n=500
57 Correct 26 ms 24056 KB n=500
58 Correct 31 ms 23928 KB n=500

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23800 KB n=5
2 Correct 24 ms 23800 KB n=100
3 Correct 23 ms 23928 KB n=100
4 Correct 23 ms 23800 KB n=100
5 Correct 23 ms 23800 KB n=100
6 Correct 28 ms 23928 KB n=100
7 Correct 28 ms 23800 KB n=100
8 Correct 24 ms 23928 KB n=100
9 Correct 23 ms 23928 KB n=100
10 Correct 23 ms 23800 KB n=100
11 Correct 23 ms 23800 KB n=100
12 Correct 23 ms 23800 KB n=100
13 Correct 24 ms 23800 KB n=100
14 Correct 24 ms 23800 KB n=100
15 Correct 28 ms 23804 KB n=100
16 Correct 28 ms 23860 KB n=100
17 Correct 29 ms 23800 KB n=100
18 Correct 24 ms 23800 KB n=100
19 Correct 26 ms 23928 KB n=100
20 Correct 24 ms 23800 KB n=100
21 Correct 27 ms 23928 KB n=100
22 Correct 28 ms 23996 KB n=100
23 Correct 31 ms 23800 KB n=100
24 Correct 26 ms 23884 KB n=100
25 Correct 24 ms 23800 KB n=100
26 Correct 29 ms 23800 KB n=12
27 Correct 28 ms 23796 KB n=100
28 Correct 31 ms 23928 KB n=500
29 Correct 31 ms 23936 KB n=500
30 Correct 26 ms 23960 KB n=500
31 Correct 34 ms 23928 KB n=500
32 Correct 26 ms 23928 KB n=500
33 Correct 25 ms 23928 KB n=500
34 Correct 30 ms 23928 KB n=500
35 Correct 27 ms 23928 KB n=500
36 Correct 29 ms 23960 KB n=500
37 Correct 31 ms 23928 KB n=500
38 Correct 26 ms 23928 KB n=500
39 Correct 29 ms 24056 KB n=500
40 Correct 32 ms 23928 KB n=500
41 Correct 31 ms 23928 KB n=500
42 Correct 30 ms 23928 KB n=500
43 Correct 31 ms 24000 KB n=500
44 Correct 26 ms 23928 KB n=500
45 Correct 30 ms 23980 KB n=500
46 Correct 26 ms 23928 KB n=500
47 Correct 28 ms 24028 KB n=500
48 Correct 27 ms 23928 KB n=500
49 Correct 26 ms 24056 KB n=500
50 Correct 30 ms 23932 KB n=500
51 Correct 26 ms 23928 KB n=500
52 Correct 26 ms 23928 KB n=500
53 Correct 31 ms 23944 KB n=500
54 Correct 26 ms 23928 KB n=500
55 Correct 24 ms 23928 KB n=278
56 Correct 26 ms 23932 KB n=500
57 Correct 26 ms 24056 KB n=500
58 Correct 31 ms 23928 KB n=500
59 Correct 40 ms 24440 KB n=2000
60 Correct 39 ms 24528 KB n=2000
61 Correct 34 ms 24440 KB n=2000
62 Correct 40 ms 24440 KB n=2000
63 Correct 39 ms 24440 KB n=2000
64 Correct 39 ms 24440 KB n=2000
65 Correct 60 ms 24440 KB n=2000
66 Correct 35 ms 24440 KB n=2000
67 Correct 34 ms 24440 KB n=2000
68 Correct 34 ms 24440 KB n=2000
69 Correct 36 ms 24440 KB n=2000
70 Correct 36 ms 24312 KB n=2000
71 Correct 36 ms 24308 KB n=2000
72 Correct 37 ms 24312 KB n=2000
73 Correct 36 ms 24412 KB n=2000
74 Correct 32 ms 24312 KB n=1844
75 Correct 37 ms 24312 KB n=2000
76 Correct 34 ms 24316 KB n=2000
77 Correct 35 ms 24436 KB n=2000
78 Correct 34 ms 24312 KB n=2000
79 Correct 33 ms 24312 KB n=2000
80 Correct 34 ms 24444 KB n=2000
81 Correct 35 ms 24440 KB n=2000
82 Correct 33 ms 24312 KB n=2000
83 Correct 34 ms 24440 KB n=2000
84 Correct 36 ms 24440 KB n=2000
85 Correct 34 ms 24360 KB n=2000
86 Correct 35 ms 24312 KB n=2000
87 Correct 34 ms 24312 KB n=2000
88 Correct 35 ms 24424 KB n=2000
89 Correct 34 ms 24440 KB n=2000
90 Correct 34 ms 24440 KB n=2000
91 Correct 36 ms 24316 KB n=2000

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23800 KB n=5
2 Correct 24 ms 23800 KB n=100
3 Correct 23 ms 23928 KB n=100
4 Correct 23 ms 23800 KB n=100
5 Correct 23 ms 23800 KB n=100
6 Correct 28 ms 23928 KB n=100
7 Correct 28 ms 23800 KB n=100
8 Correct 24 ms 23928 KB n=100
9 Correct 23 ms 23928 KB n=100
10 Correct 23 ms 23800 KB n=100
11 Correct 23 ms 23800 KB n=100
12 Correct 23 ms 23800 KB n=100
13 Correct 24 ms 23800 KB n=100
14 Correct 24 ms 23800 KB n=100
15 Correct 28 ms 23804 KB n=100
16 Correct 28 ms 23860 KB n=100
17 Correct 29 ms 23800 KB n=100
18 Correct 24 ms 23800 KB n=100
19 Correct 26 ms 23928 KB n=100
20 Correct 24 ms 23800 KB n=100
21 Correct 27 ms 23928 KB n=100
22 Correct 28 ms 23996 KB n=100
23 Correct 31 ms 23800 KB n=100
24 Correct 26 ms 23884 KB n=100
25 Correct 24 ms 23800 KB n=100
26 Correct 29 ms 23800 KB n=12
27 Correct 28 ms 23796 KB n=100
28 Correct 31 ms 23928 KB n=500
29 Correct 31 ms 23936 KB n=500
30 Correct 26 ms 23960 KB n=500
31 Correct 34 ms 23928 KB n=500
32 Correct 26 ms 23928 KB n=500
33 Correct 25 ms 23928 KB n=500
34 Correct 30 ms 23928 KB n=500
35 Correct 27 ms 23928 KB n=500
36 Correct 29 ms 23960 KB n=500
37 Correct 31 ms 23928 KB n=500
38 Correct 26 ms 23928 KB n=500
39 Correct 29 ms 24056 KB n=500
40 Correct 32 ms 23928 KB n=500
41 Correct 31 ms 23928 KB n=500
42 Correct 30 ms 23928 KB n=500
43 Correct 31 ms 24000 KB n=500
44 Correct 26 ms 23928 KB n=500
45 Correct 30 ms 23980 KB n=500
46 Correct 26 ms 23928 KB n=500
47 Correct 28 ms 24028 KB n=500
48 Correct 27 ms 23928 KB n=500
49 Correct 26 ms 24056 KB n=500
50 Correct 30 ms 23932 KB n=500
51 Correct 26 ms 23928 KB n=500
52 Correct 26 ms 23928 KB n=500
53 Correct 31 ms 23944 KB n=500
54 Correct 26 ms 23928 KB n=500
55 Correct 24 ms 23928 KB n=278
56 Correct 26 ms 23932 KB n=500
57 Correct 26 ms 24056 KB n=500
58 Correct 31 ms 23928 KB n=500
59 Correct 40 ms 24440 KB n=2000
60 Correct 39 ms 24528 KB n=2000
61 Correct 34 ms 24440 KB n=2000
62 Correct 40 ms 24440 KB n=2000
63 Correct 39 ms 24440 KB n=2000
64 Correct 39 ms 24440 KB n=2000
65 Correct 60 ms 24440 KB n=2000
66 Correct 35 ms 24440 KB n=2000
67 Correct 34 ms 24440 KB n=2000
68 Correct 34 ms 24440 KB n=2000
69 Correct 36 ms 24440 KB n=2000
70 Correct 36 ms 24312 KB n=2000
71 Correct 36 ms 24308 KB n=2000
72 Correct 37 ms 24312 KB n=2000
73 Correct 36 ms 24412 KB n=2000
74 Correct 32 ms 24312 KB n=1844
75 Correct 37 ms 24312 KB n=2000
76 Correct 34 ms 24316 KB n=2000
77 Correct 35 ms 24436 KB n=2000
78 Correct 34 ms 24312 KB n=2000
79 Correct 33 ms 24312 KB n=2000
80 Correct 34 ms 24444 KB n=2000
81 Correct 35 ms 24440 KB n=2000
82 Correct 33 ms 24312 KB n=2000
83 Correct 34 ms 24440 KB n=2000
84 Correct 36 ms 24440 KB n=2000
85 Correct 34 ms 24360 KB n=2000
86 Correct 35 ms 24312 KB n=2000
87 Correct 34 ms 24312 KB n=2000
88 Correct 35 ms 24424 KB n=2000
89 Correct 34 ms 24440 KB n=2000
90 Correct 34 ms 24440 KB n=2000
91 Correct 36 ms 24316 KB n=2000
92 Correct 1600 ms 79408 KB n=200000
93 Correct 2036 ms 84180 KB n=200000
94 Correct 2012 ms 87608 KB n=200000
95 Correct 1572 ms 79100 KB n=200000
96 Correct 1564 ms 79212 KB n=200000
97 Correct 2077 ms 83216 KB n=200000
98 Correct 1670 ms 79068 KB n=200000
99 Correct 2037 ms 79448 KB n=200000
100 Correct 1713 ms 79272 KB n=200000
101 Correct 2037 ms 88744 KB n=200000
102 Correct 1716 ms 80476 KB n=200000
103 Correct 1564 ms 80396 KB n=200000
104 Correct 1745 ms 80276 KB n=200000
105 Correct 1616 ms 80788 KB n=200000
106 Correct 1646 ms 80720 KB n=200000
107 Correct 1659 ms 80660 KB n=200000
108 Correct 1899 ms 79204 KB n=200000
109 Correct 1777 ms 79492 KB n=200000
110 Correct 1835 ms 79304 KB n=200000
111 Correct 1575 ms 78520 KB n=200000
112 Correct 2033 ms 87724 KB n=200000
113 Correct 2105 ms 83340 KB n=200000
114 Correct 1588 ms 78720 KB n=200000
115 Correct 2321 ms 81076 KB n=200000
116 Correct 1605 ms 79404 KB n=200000
117 Correct 2001 ms 88292 KB n=200000
118 Correct 2105 ms 82116 KB n=200000
119 Correct 1704 ms 79232 KB n=200000
120 Correct 2056 ms 87820 KB n=200000
121 Correct 2353 ms 87744 KB n=200000
122 Correct 2072 ms 88016 KB n=200000
123 Correct 1624 ms 80556 KB n=200000
124 Correct 501 ms 39696 KB n=25264