oj.uz

Submission #492370

# Submission time Handle Problem Language Result Execution time Memory
492370 2021-12-07T03:16:24 Z phamhoanghiep Birthday gift (IZhO18_treearray) C++14
100 / 100
 1251 ms 62232 KB 
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
const int maxn=2e5+5;
int n,m,q;
vector<int> AdjList[maxn];
int up[maxn][20];
int in[maxn];
int out[maxn];
int arr[maxn];
int timer=0;
bool ancestor(int a, int b) {
    if(!a) return 1;
    if(!b) return 0;
    return in[a]<=in[b]&&out[a]>=out[b];
}
void dfs(int s, int p=0) {
    in[s]=++timer;
    //cout<<"in "<<s<<" = "<<in[s]<<endl;
    up[s][0]=p;
    for(int i=1 ; i<20 ; i++) up[s][i]=up[up[s][i-1]][i-1];
    for(int u: AdjList[s]) {
        if(u==p) continue;
        dfs(u,s);
    }
    out[s]=timer;
    //cout<<"out "<<s<<" = "<<out[s]<<endl;
}
int lca(int u, int v) {
    //cout<<"lca "<<u<<" "<<v<<" = ";
    if(ancestor(u,v)) return u;
    if(ancestor(v,u)) return v;
    for(int i=19 ; i>=0 ; i--) {
        if(!ancestor(up[u][i],v)) u=up[u][i];
    }
    //cout<<up[u][0]<<endl;
    return up[u][0];
}
// build segment tree
int lc[maxn]; // between two adjacent in array
set<ii> S;
set<ii> V;
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n>>m>>q;
    for(int i=1 ; i<n ; i++) {
        int u,v;
        cin>>u>>v;
        AdjList[u].push_back(v);
        AdjList[v].push_back(u);
    }
    dfs(1);
    for(int i=1 ; i<=m ; i++) {
        cin>>arr[i];
        V.insert(ii(arr[i],i));
    }
    for(int i=1 ; i<m ; i++) {
        lc[i]=lca(arr[i],arr[i+1]);
        S.insert(ii(lc[i],i));
        // cout<<"S "<<lc[i]<<" "<<i<<endl;
    }
    while(q--) {
        int type,l,r,v;
        cin>>type;
        if(type==2) {
            cin>>l>>r>>v;
            auto it1=V.lower_bound(ii(v,l));
            auto it=S.lower_bound(ii(v,l));
            if(it1!=V.end()) {
                if((*it1).first==v&&(*it1).second<=r) {
                    cout<<(*it1).second<<' '<<(*it1).second<<'\n';
                    continue;
                }
            }
            if(m==1) {
                cout<<"-1 -1\n";
                continue;
            }
            if(it==S.end()) {
                cout<<"-1 -1\n";
                continue;
            }
            else {
                //cout<<"find = "<<(*it).first<<" "<<(*it).second<<endl;
                if((*it).first!=v) {
                    cout<<"-1 -1\n";
                    continue;
                }
                else if((*it).second>=r) {
                    cout<<"-1 -1\n";
                    continue;
                }
                else cout<<(*it).second<<' '<<(*it).second+1<<'\n';
            }
        }
        else {
            cin>>l>>v;
            auto it1=V.find(ii(arr[l],l));
            V.erase(it1);
            arr[l]=v;
            V.insert(ii(arr[l],l));
            if(l!=m) {
                auto it=S.find(ii(lc[l],l));
                S.erase(it);
                lc[l]=lca(arr[l],arr[l+1]);
                //cout<<"lc "<<l<<" = "<<lc[l]<<endl;
                S.insert(ii(lc[l],l));
            }
            if(l!=1) {
                auto it=S.find(ii(lc[l-1],l-1));
                S.erase(it);
                lc[l-1]=lca(arr[l-1],arr[l]);
                //cout<<"lc "<<l-1<<" = "<<lc[l-1]<<endl;
                S.insert(ii(lc[l-1],l-1));
            }
        }
    }
}

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4940 KB n=5
2 Correct 2 ms 4940 KB n=100
3 Correct 3 ms 4940 KB n=100
4 Correct 3 ms 4940 KB n=100
5 Correct 3 ms 4940 KB n=100
6 Correct 3 ms 4940 KB n=100
7 Correct 3 ms 4940 KB n=100
8 Correct 3 ms 4940 KB n=100
9 Correct 4 ms 4940 KB n=100
10 Correct 3 ms 4940 KB n=100
11 Correct 3 ms 4940 KB n=100
12 Correct 3 ms 4956 KB n=100
13 Correct 3 ms 4940 KB n=100
14 Correct 3 ms 4940 KB n=100
15 Correct 3 ms 4940 KB n=100
16 Correct 3 ms 4940 KB n=100
17 Correct 3 ms 4940 KB n=100
18 Correct 3 ms 4940 KB n=100
19 Correct 4 ms 4940 KB n=100
20 Correct 3 ms 4992 KB n=100
21 Correct 3 ms 4940 KB n=100
22 Correct 3 ms 4940 KB n=100
23 Correct 3 ms 4940 KB n=100
24 Correct 3 ms 4940 KB n=100
25 Correct 3 ms 4940 KB n=100
26 Correct 2 ms 4940 KB n=12
27 Correct 3 ms 4940 KB n=100
28 Correct 3 ms 5068 KB n=500
29 Correct 5 ms 5160 KB n=500
30 Correct 4 ms 5068 KB n=500
31 Correct 4 ms 5068 KB n=500
32 Correct 5 ms 5208 KB n=500
33 Correct 3 ms 5068 KB n=500
34 Correct 4 ms 5068 KB n=500
35 Correct 3 ms 5068 KB n=500
36 Correct 4 ms 5068 KB n=500
37 Correct 4 ms 5068 KB n=500
38 Correct 3 ms 5148 KB n=500
39 Correct 3 ms 5068 KB n=500
40 Correct 3 ms 5152 KB n=500
41 Correct 4 ms 5152 KB n=500
42 Correct 4 ms 5068 KB n=500
43 Correct 4 ms 5068 KB n=500
44 Correct 3 ms 5068 KB n=500
45 Correct 3 ms 5084 KB n=500
46 Correct 3 ms 5068 KB n=500
47 Correct 3 ms 5068 KB n=500
48 Correct 3 ms 5068 KB n=500
49 Correct 3 ms 5068 KB n=500
50 Correct 3 ms 5068 KB n=500
51 Correct 4 ms 5068 KB n=500
52 Correct 4 ms 5160 KB n=500
53 Correct 5 ms 5068 KB n=500
54 Correct 4 ms 5068 KB n=500
55 Correct 3 ms 5068 KB n=278
56 Correct 3 ms 5068 KB n=500
57 Correct 4 ms 5068 KB n=500
58 Correct 3 ms 5068 KB n=500

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4940 KB n=5
2 Correct 2 ms 4940 KB n=100
3 Correct 3 ms 4940 KB n=100
4 Correct 3 ms 4940 KB n=100
5 Correct 3 ms 4940 KB n=100
6 Correct 3 ms 4940 KB n=100
7 Correct 3 ms 4940 KB n=100
8 Correct 3 ms 4940 KB n=100
9 Correct 4 ms 4940 KB n=100
10 Correct 3 ms 4940 KB n=100
11 Correct 3 ms 4940 KB n=100
12 Correct 3 ms 4956 KB n=100
13 Correct 3 ms 4940 KB n=100
14 Correct 3 ms 4940 KB n=100
15 Correct 3 ms 4940 KB n=100
16 Correct 3 ms 4940 KB n=100
17 Correct 3 ms 4940 KB n=100
18 Correct 3 ms 4940 KB n=100
19 Correct 4 ms 4940 KB n=100
20 Correct 3 ms 4992 KB n=100
21 Correct 3 ms 4940 KB n=100
22 Correct 3 ms 4940 KB n=100
23 Correct 3 ms 4940 KB n=100
24 Correct 3 ms 4940 KB n=100
25 Correct 3 ms 4940 KB n=100
26 Correct 2 ms 4940 KB n=12
27 Correct 3 ms 4940 KB n=100
28 Correct 3 ms 5068 KB n=500
29 Correct 5 ms 5160 KB n=500
30 Correct 4 ms 5068 KB n=500
31 Correct 4 ms 5068 KB n=500
32 Correct 5 ms 5208 KB n=500
33 Correct 3 ms 5068 KB n=500
34 Correct 4 ms 5068 KB n=500
35 Correct 3 ms 5068 KB n=500
36 Correct 4 ms 5068 KB n=500
37 Correct 4 ms 5068 KB n=500
38 Correct 3 ms 5148 KB n=500
39 Correct 3 ms 5068 KB n=500
40 Correct 3 ms 5152 KB n=500
41 Correct 4 ms 5152 KB n=500
42 Correct 4 ms 5068 KB n=500
43 Correct 4 ms 5068 KB n=500
44 Correct 3 ms 5068 KB n=500
45 Correct 3 ms 5084 KB n=500
46 Correct 3 ms 5068 KB n=500
47 Correct 3 ms 5068 KB n=500
48 Correct 3 ms 5068 KB n=500
49 Correct 3 ms 5068 KB n=500
50 Correct 3 ms 5068 KB n=500
51 Correct 4 ms 5068 KB n=500
52 Correct 4 ms 5160 KB n=500
53 Correct 5 ms 5068 KB n=500
54 Correct 4 ms 5068 KB n=500
55 Correct 3 ms 5068 KB n=278
56 Correct 3 ms 5068 KB n=500
57 Correct 4 ms 5068 KB n=500
58 Correct 3 ms 5068 KB n=500
59 Correct 5 ms 5452 KB n=2000
60 Correct 6 ms 5580 KB n=2000
61 Correct 6 ms 5580 KB n=2000
62 Correct 7 ms 5452 KB n=2000
63 Correct 7 ms 5540 KB n=2000
64 Correct 8 ms 5580 KB n=2000
65 Correct 6 ms 5452 KB n=2000
66 Correct 6 ms 5580 KB n=2000
67 Correct 8 ms 5452 KB n=2000
68 Correct 7 ms 5580 KB n=2000
69 Correct 5 ms 5452 KB n=2000
70 Correct 5 ms 5452 KB n=2000
71 Correct 6 ms 5484 KB n=2000
72 Correct 6 ms 5588 KB n=2000
73 Correct 5 ms 5452 KB n=2000
74 Correct 6 ms 5452 KB n=1844
75 Correct 5 ms 5452 KB n=2000
76 Correct 7 ms 5452 KB n=2000
77 Correct 9 ms 5536 KB n=2000
78 Correct 6 ms 5452 KB n=2000
79 Correct 6 ms 5452 KB n=2000
80 Correct 6 ms 5544 KB n=2000
81 Correct 7 ms 5452 KB n=2000
82 Correct 9 ms 5452 KB n=2000
83 Correct 6 ms 5580 KB n=2000
84 Correct 6 ms 5452 KB n=2000
85 Correct 7 ms 5580 KB n=2000
86 Correct 9 ms 5556 KB n=2000
87 Correct 6 ms 5452 KB n=2000
88 Correct 6 ms 5536 KB n=2000
89 Correct 6 ms 5580 KB n=2000
90 Correct 7 ms 5528 KB n=2000
91 Correct 5 ms 5452 KB n=2000

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4940 KB n=5
2 Correct 2 ms 4940 KB n=100
3 Correct 3 ms 4940 KB n=100
4 Correct 3 ms 4940 KB n=100
5 Correct 3 ms 4940 KB n=100
6 Correct 3 ms 4940 KB n=100
7 Correct 3 ms 4940 KB n=100
8 Correct 3 ms 4940 KB n=100
9 Correct 4 ms 4940 KB n=100
10 Correct 3 ms 4940 KB n=100
11 Correct 3 ms 4940 KB n=100
12 Correct 3 ms 4956 KB n=100
13 Correct 3 ms 4940 KB n=100
14 Correct 3 ms 4940 KB n=100
15 Correct 3 ms 4940 KB n=100
16 Correct 3 ms 4940 KB n=100
17 Correct 3 ms 4940 KB n=100
18 Correct 3 ms 4940 KB n=100
19 Correct 4 ms 4940 KB n=100
20 Correct 3 ms 4992 KB n=100
21 Correct 3 ms 4940 KB n=100
22 Correct 3 ms 4940 KB n=100
23 Correct 3 ms 4940 KB n=100
24 Correct 3 ms 4940 KB n=100
25 Correct 3 ms 4940 KB n=100
26 Correct 2 ms 4940 KB n=12
27 Correct 3 ms 4940 KB n=100
28 Correct 3 ms 5068 KB n=500
29 Correct 5 ms 5160 KB n=500
30 Correct 4 ms 5068 KB n=500
31 Correct 4 ms 5068 KB n=500
32 Correct 5 ms 5208 KB n=500
33 Correct 3 ms 5068 KB n=500
34 Correct 4 ms 5068 KB n=500
35 Correct 3 ms 5068 KB n=500
36 Correct 4 ms 5068 KB n=500
37 Correct 4 ms 5068 KB n=500
38 Correct 3 ms 5148 KB n=500
39 Correct 3 ms 5068 KB n=500
40 Correct 3 ms 5152 KB n=500
41 Correct 4 ms 5152 KB n=500
42 Correct 4 ms 5068 KB n=500
43 Correct 4 ms 5068 KB n=500
44 Correct 3 ms 5068 KB n=500
45 Correct 3 ms 5084 KB n=500
46 Correct 3 ms 5068 KB n=500
47 Correct 3 ms 5068 KB n=500
48 Correct 3 ms 5068 KB n=500
49 Correct 3 ms 5068 KB n=500
50 Correct 3 ms 5068 KB n=500
51 Correct 4 ms 5068 KB n=500
52 Correct 4 ms 5160 KB n=500
53 Correct 5 ms 5068 KB n=500
54 Correct 4 ms 5068 KB n=500
55 Correct 3 ms 5068 KB n=278
56 Correct 3 ms 5068 KB n=500
57 Correct 4 ms 5068 KB n=500
58 Correct 3 ms 5068 KB n=500
59 Correct 5 ms 5452 KB n=2000
60 Correct 6 ms 5580 KB n=2000
61 Correct 6 ms 5580 KB n=2000
62 Correct 7 ms 5452 KB n=2000
63 Correct 7 ms 5540 KB n=2000
64 Correct 8 ms 5580 KB n=2000
65 Correct 6 ms 5452 KB n=2000
66 Correct 6 ms 5580 KB n=2000
67 Correct 8 ms 5452 KB n=2000
68 Correct 7 ms 5580 KB n=2000
69 Correct 5 ms 5452 KB n=2000
70 Correct 5 ms 5452 KB n=2000
71 Correct 6 ms 5484 KB n=2000
72 Correct 6 ms 5588 KB n=2000
73 Correct 5 ms 5452 KB n=2000
74 Correct 6 ms 5452 KB n=1844
75 Correct 5 ms 5452 KB n=2000
76 Correct 7 ms 5452 KB n=2000
77 Correct 9 ms 5536 KB n=2000
78 Correct 6 ms 5452 KB n=2000
79 Correct 6 ms 5452 KB n=2000
80 Correct 6 ms 5544 KB n=2000
81 Correct 7 ms 5452 KB n=2000
82 Correct 9 ms 5452 KB n=2000
83 Correct 6 ms 5580 KB n=2000
84 Correct 6 ms 5452 KB n=2000
85 Correct 7 ms 5580 KB n=2000
86 Correct 9 ms 5556 KB n=2000
87 Correct 6 ms 5452 KB n=2000
88 Correct 6 ms 5536 KB n=2000
89 Correct 6 ms 5580 KB n=2000
90 Correct 7 ms 5528 KB n=2000
91 Correct 5 ms 5452 KB n=2000
92 Correct 772 ms 53748 KB n=200000
93 Correct 1251 ms 57648 KB n=200000
94 Correct 1072 ms 60948 KB n=200000
95 Correct 741 ms 53660 KB n=200000
96 Correct 815 ms 53700 KB n=200000
97 Correct 1181 ms 56688 KB n=200000
98 Correct 779 ms 53772 KB n=200000
99 Correct 914 ms 53136 KB n=200000
100 Correct 794 ms 53848 KB n=200000
101 Correct 939 ms 62232 KB n=200000
102 Correct 416 ms 54636 KB n=200000
103 Correct 469 ms 54724 KB n=200000
104 Correct 426 ms 54776 KB n=200000
105 Correct 432 ms 54532 KB n=200000
106 Correct 420 ms 54596 KB n=200000
107 Correct 428 ms 54404 KB n=200000
108 Correct 782 ms 53316 KB n=200000
109 Correct 768 ms 53420 KB n=200000
110 Correct 801 ms 53600 KB n=200000
111 Correct 751 ms 53320 KB n=200000
112 Correct 954 ms 61248 KB n=200000
113 Correct 1098 ms 56624 KB n=200000
114 Correct 701 ms 53260 KB n=200000
115 Correct 1237 ms 54652 KB n=200000
116 Correct 730 ms 53620 KB n=200000
117 Correct 945 ms 61604 KB n=200000
118 Correct 1130 ms 55464 KB n=200000
119 Correct 722 ms 53628 KB n=200000
120 Correct 710 ms 61636 KB n=200000
121 Correct 769 ms 61604 KB n=200000
122 Correct 812 ms 62168 KB n=200000
123 Correct 424 ms 53844 KB n=200000
124 Correct 255 ms 20100 KB n=25264