oj.uz

Submission #171854

# Submission time Handle Problem Language Result Execution time Memory
171854 2019-12-30T13:41:49 Z RafaelSus Birthday gift (IZhO18_treearray) C++14
100 / 100
 2291 ms 75768 KB 
#include <bits/stdc++.h>
 
using namespace std;
const int N = 2e5 + 5;
typedef long long ll;
const ll inf=1e15;
#define pb push_back
const int INF=(0x3f3f3f3f);
 
vector<int>g[N];
int a[N];
int timer,tin[N],tout[N];
int up[20][N];
 
void dfs(int v,int p){
  up[0][v]=p;
  tin[v]=++timer;
  for(int i=1;i<=19;i++){
    up[i][v]=up[i-1][up[i-1][v]];
  }
  for(auto to:g[v])
    if(to!=p)dfs(to,v);
  tout[v]=++timer;
}
 
bool upper(int a,int b){
  return tin[a]<=tin[b]&&tout[a]>=tout[b];
}
 
int lca(int a,int b){
  if(upper(a,b))return a;
  if(upper(b,a))return b;
  for(int i=19;i>=0;--i){
    if(!upper(up[i][a],b)){
      a=up[i][a];
      //cerr<<a<<' ';
    }
  }
  return up[0][a];
}

set<pair<int,int>>s[N];

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);cout.tie(0);
 
  int n,m,q;
  cin>>n>>m>>q;
  for(int i=0;i<n-1;i++){
    int a,b;
    cin>>a>>b;
    g[a].pb(b);
    g[b].pb(a);
  }
  dfs(1,1);
  for(int i=1;i<=m;i++){
    cin>>a[i];
    s[a[i]].insert({i,i});
    if(i>1)s[lca(a[i-1],a[i])].insert({i-1,i});
  }
   
  /*for(int i=1;i<=n;i++){
    cout<<i<<"        ";
    for(auto x:s[i])
      cout<<x.first<<' '<<x.second<<" | ";
    cout<<'\n';
  } */
   
  for(int i=0;i<q;i++){
    int com;
    cin>>com;
    if(com==1){
      int p,v;
      cin>>p>>v;
      s[a[p]].erase({p,p});
      if(p>1)s[lca(a[p-1],a[p])].erase({p-1,p});
      if(p<m)s[lca(a[p],a[p+1])].erase({p,p+1});
      a[p]=v;
      s[a[p]].insert({p,p});
      if(p>1)s[lca(a[p-1],a[p])].insert({p-1,p});
      if(p<m)s[lca(a[p],a[p+1])].insert({p,p+1});
    }else{
      int l,r,v;
      cin>>l>>r>>v;
      int le=-1,ri=-1;
      auto it=s[v].lower_bound({l,0});
      if(it!=s[v].end()){
        if(it->second<=r){
          le=it->first;
          ri=it->second;
        }
        //cerr<<it->first<<' '<<it->second<<'\n';
      }
      cout<<le<<' '<<ri<<'\n';
    }
  }
}

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 14712 KB n=5
2 Correct 15 ms 14584 KB n=100
3 Correct 15 ms 14584 KB n=100
4 Correct 18 ms 14584 KB n=100
5 Correct 15 ms 14584 KB n=100
6 Correct 17 ms 14584 KB n=100
7 Correct 16 ms 14584 KB n=100
8 Correct 15 ms 14584 KB n=100
9 Correct 18 ms 14584 KB n=100
10 Correct 15 ms 14584 KB n=100
11 Correct 21 ms 14584 KB n=100
12 Correct 14 ms 14584 KB n=100
13 Correct 15 ms 14584 KB n=100
14 Correct 18 ms 14584 KB n=100
15 Correct 15 ms 14584 KB n=100
16 Correct 15 ms 14584 KB n=100
17 Correct 15 ms 14584 KB n=100
18 Correct 14 ms 14588 KB n=100
19 Correct 15 ms 14584 KB n=100
20 Correct 15 ms 14584 KB n=100
21 Correct 15 ms 14584 KB n=100
22 Correct 15 ms 14584 KB n=100
23 Correct 15 ms 14584 KB n=100
24 Correct 15 ms 14584 KB n=100
25 Correct 15 ms 14584 KB n=100
26 Correct 15 ms 14584 KB n=12
27 Correct 15 ms 14584 KB n=100
28 Correct 16 ms 14756 KB n=500
29 Correct 15 ms 14712 KB n=500
30 Correct 16 ms 14712 KB n=500
31 Correct 16 ms 14712 KB n=500
32 Correct 16 ms 14712 KB n=500
33 Correct 16 ms 14716 KB n=500
34 Correct 16 ms 14712 KB n=500
35 Correct 15 ms 14716 KB n=500
36 Correct 15 ms 14712 KB n=500
37 Correct 16 ms 14712 KB n=500
38 Correct 15 ms 14712 KB n=500
39 Correct 16 ms 14712 KB n=500
40 Correct 16 ms 14712 KB n=500
41 Correct 16 ms 14716 KB n=500
42 Correct 16 ms 14712 KB n=500
43 Correct 16 ms 14712 KB n=500
44 Correct 16 ms 14712 KB n=500
45 Correct 16 ms 14712 KB n=500
46 Correct 15 ms 14712 KB n=500
47 Correct 16 ms 14712 KB n=500
48 Correct 16 ms 14712 KB n=500
49 Correct 16 ms 14712 KB n=500
50 Correct 16 ms 14712 KB n=500
51 Correct 16 ms 14712 KB n=500
52 Correct 15 ms 14712 KB n=500
53 Correct 16 ms 14712 KB n=500
54 Correct 15 ms 14712 KB n=500
55 Correct 15 ms 14584 KB n=278
56 Correct 15 ms 14712 KB n=500
57 Correct 15 ms 14712 KB n=500
58 Correct 16 ms 14712 KB n=500
59 Correct 21 ms 15096 KB n=2000
60 Correct 18 ms 15096 KB n=2000
61 Correct 18 ms 15096 KB n=2000
62 Correct 20 ms 15096 KB n=2000
63 Correct 21 ms 15100 KB n=2000
64 Correct 19 ms 15096 KB n=2000
65 Correct 20 ms 15096 KB n=2000
66 Correct 19 ms 15096 KB n=2000
67 Correct 21 ms 15096 KB n=2000
68 Correct 19 ms 15096 KB n=2000
69 Correct 18 ms 15096 KB n=2000
70 Correct 18 ms 15096 KB n=2000
71 Correct 19 ms 15224 KB n=2000
72 Correct 19 ms 15096 KB n=2000
73 Correct 22 ms 15096 KB n=2000
74 Correct 20 ms 15096 KB n=1844
75 Correct 19 ms 15096 KB n=2000
76 Correct 21 ms 15100 KB n=2000
77 Correct 21 ms 15096 KB n=2000
78 Correct 21 ms 15096 KB n=2000
79 Correct 20 ms 15096 KB n=2000
80 Correct 18 ms 15096 KB n=2000
81 Correct 19 ms 15096 KB n=2000
82 Correct 20 ms 15068 KB n=2000
83 Correct 19 ms 15096 KB n=2000
84 Correct 21 ms 15096 KB n=2000
85 Correct 20 ms 15096 KB n=2000
86 Correct 20 ms 15096 KB n=2000
87 Correct 21 ms 15096 KB n=2000
88 Correct 18 ms 15100 KB n=2000
89 Correct 19 ms 15144 KB n=2000
90 Correct 19 ms 15224 KB n=2000
91 Correct 26 ms 15096 KB n=2000

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 14712 KB n=5
2 Correct 15 ms 14584 KB n=100
3 Correct 15 ms 14584 KB n=100
4 Correct 18 ms 14584 KB n=100
5 Correct 15 ms 14584 KB n=100
6 Correct 17 ms 14584 KB n=100
7 Correct 16 ms 14584 KB n=100
8 Correct 15 ms 14584 KB n=100
9 Correct 18 ms 14584 KB n=100
10 Correct 15 ms 14584 KB n=100
11 Correct 21 ms 14584 KB n=100
12 Correct 14 ms 14584 KB n=100
13 Correct 15 ms 14584 KB n=100
14 Correct 18 ms 14584 KB n=100
15 Correct 15 ms 14584 KB n=100
16 Correct 15 ms 14584 KB n=100
17 Correct 15 ms 14584 KB n=100
18 Correct 14 ms 14588 KB n=100
19 Correct 15 ms 14584 KB n=100
20 Correct 15 ms 14584 KB n=100
21 Correct 15 ms 14584 KB n=100
22 Correct 15 ms 14584 KB n=100
23 Correct 15 ms 14584 KB n=100
24 Correct 15 ms 14584 KB n=100
25 Correct 15 ms 14584 KB n=100
26 Correct 15 ms 14584 KB n=12
27 Correct 15 ms 14584 KB n=100
28 Correct 16 ms 14756 KB n=500
29 Correct 15 ms 14712 KB n=500
30 Correct 16 ms 14712 KB n=500
31 Correct 16 ms 14712 KB n=500
32 Correct 16 ms 14712 KB n=500
33 Correct 16 ms 14716 KB n=500
34 Correct 16 ms 14712 KB n=500
35 Correct 15 ms 14716 KB n=500
36 Correct 15 ms 14712 KB n=500
37 Correct 16 ms 14712 KB n=500
38 Correct 15 ms 14712 KB n=500
39 Correct 16 ms 14712 KB n=500
40 Correct 16 ms 14712 KB n=500
41 Correct 16 ms 14716 KB n=500
42 Correct 16 ms 14712 KB n=500
43 Correct 16 ms 14712 KB n=500
44 Correct 16 ms 14712 KB n=500
45 Correct 16 ms 14712 KB n=500
46 Correct 15 ms 14712 KB n=500
47 Correct 16 ms 14712 KB n=500
48 Correct 16 ms 14712 KB n=500
49 Correct 16 ms 14712 KB n=500
50 Correct 16 ms 14712 KB n=500
51 Correct 16 ms 14712 KB n=500
52 Correct 15 ms 14712 KB n=500
53 Correct 16 ms 14712 KB n=500
54 Correct 15 ms 14712 KB n=500
55 Correct 15 ms 14584 KB n=278
56 Correct 15 ms 14712 KB n=500
57 Correct 15 ms 14712 KB n=500
58 Correct 16 ms 14712 KB n=500
59 Correct 21 ms 15096 KB n=2000
60 Correct 18 ms 15096 KB n=2000
61 Correct 18 ms 15096 KB n=2000
62 Correct 20 ms 15096 KB n=2000
63 Correct 21 ms 15100 KB n=2000
64 Correct 19 ms 15096 KB n=2000
65 Correct 20 ms 15096 KB n=2000
66 Correct 19 ms 15096 KB n=2000
67 Correct 21 ms 15096 KB n=2000
68 Correct 19 ms 15096 KB n=2000
69 Correct 18 ms 15096 KB n=2000
70 Correct 18 ms 15096 KB n=2000
71 Correct 19 ms 15224 KB n=2000
72 Correct 19 ms 15096 KB n=2000
73 Correct 22 ms 15096 KB n=2000
74 Correct 20 ms 15096 KB n=1844
75 Correct 19 ms 15096 KB n=2000
76 Correct 21 ms 15100 KB n=2000
77 Correct 21 ms 15096 KB n=2000
78 Correct 21 ms 15096 KB n=2000
79 Correct 20 ms 15096 KB n=2000
80 Correct 18 ms 15096 KB n=2000
81 Correct 19 ms 15096 KB n=2000
82 Correct 20 ms 15068 KB n=2000
83 Correct 19 ms 15096 KB n=2000
84 Correct 21 ms 15096 KB n=2000
85 Correct 20 ms 15096 KB n=2000
86 Correct 20 ms 15096 KB n=2000
87 Correct 21 ms 15096 KB n=2000
88 Correct 18 ms 15100 KB n=2000
89 Correct 19 ms 15144 KB n=2000
90 Correct 19 ms 15224 KB n=2000
91 Correct 26 ms 15096 KB n=2000
92 Correct 2152 ms 66260 KB n=200000
93 Correct 1339 ms 71160 KB n=200000
94 Correct 900 ms 74380 KB n=200000
95 Correct 2064 ms 66132 KB n=200000
96 Correct 2117 ms 65932 KB n=200000
97 Correct 1574 ms 70236 KB n=200000
98 Correct 2159 ms 66028 KB n=200000
99 Correct 2055 ms 66168 KB n=200000
100 Correct 2059 ms 66012 KB n=200000
101 Correct 658 ms 75768 KB n=200000
102 Correct 877 ms 67040 KB n=200000
103 Correct 881 ms 67192 KB n=200000
104 Correct 884 ms 67320 KB n=200000
105 Correct 940 ms 67556 KB n=200000
106 Correct 972 ms 67696 KB n=200000
107 Correct 879 ms 67576 KB n=200000
108 Correct 1814 ms 66152 KB n=200000
109 Correct 1823 ms 66072 KB n=200000
110 Correct 1810 ms 65912 KB n=200000
111 Correct 1708 ms 65484 KB n=200000
112 Correct 775 ms 74472 KB n=200000
113 Correct 1410 ms 69996 KB n=200000
114 Correct 1744 ms 65492 KB n=200000
115 Correct 2291 ms 67976 KB n=200000
116 Correct 1957 ms 66292 KB n=200000
117 Correct 720 ms 74844 KB n=200000
118 Correct 1687 ms 68952 KB n=200000
119 Correct 1908 ms 66184 KB n=200000
120 Correct 615 ms 74596 KB n=200000
121 Correct 623 ms 74648 KB n=200000
122 Correct 583 ms 75008 KB n=200000
123 Correct 942 ms 67340 KB n=200000
124 Correct 214 ms 29560 KB n=25264