제출 #496030

#제출 시각아이디문제언어결과실행 시간메모리
496030vinnipuh01Birthday gift (IZhO18_treearray)C++17
100 / 100
1154 ms73408 KiB
#include <iostream> #include <bits/stdc++.h> #include <cmath> #include <algorithm> #include <vector> #include <deque> #include <set> #include <stack> #include <string> #include <map> #include <queue> using namespace std; const long long oo = 1000000000000000000; long long int sum, ans = 0, mx = 0, mn = 1000000000, num, pos; /* ViHHiPuh (( `'-""``""-'` )) )-__-_.._-__-( / --- (o _ o) --- \ \ .-* ( .0. ) *-. / _'-. ,_ '=' _, .-'_ / `;#'#'# - #'#'#;` \ \_)) -----'#'----- ((_/ # --------- # '# ------- ------ #' /..-'# ------- #'-.\ _\...-\'# -- #'/-.../_ ((____)- '#' -(____)) cout << fixed << setprecision(6) << x; ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); freopen ( "sum.in", "r", stdin ) */ int x, y, l, r, a[ 200001 ], type, par[ 200001 ][ 21 ], lg = 20; vector <int> v[ 200001 ], vv; int tin[ 200001 ], tout[ 200001 ], tmr, d[ 200001 ], t[ 800001 ]; void dfs( int u, int pr = 1 ) { par[ u ][ 0 ] = pr; vv.push_back( u ); tin[ u ] = ++tmr; for ( int i = 1; i <= lg; i ++ ) par[ u ][ i ] = par[ par[ u ][ i - 1 ] ][ i - 1 ]; for ( auto to : v[ u ] ) { if ( to != pr ) { d[ to ] = d[ u ] + 1; dfs( to, u ); } } tout[ u ] = tmr; } bool ok( int a, int b ) { return ( tin[ a ] <= tin[ b ] && tout[ a ] >= tout[ b ] ); } int lca( int a, int b ) { if ( ok( a, b ) ) return a; if ( ok( b, a ) ) return b; for ( int i = lg; i >= 0; i -- ) { if ( !ok( par[ a ][ i ], b ) ) a = par[ a ][ i ]; } return par[ a ][ 0 ]; } void build( int v, int tl, int tr ) { if ( tl == tr ) { t[ v ] = a[ tl ]; return; } int mid = ( tl + tr ) / 2; build( v + v, tl, mid ); build( v + v + 1, mid + 1, tr ); t[ v ] = lca( t[ v + v ], t[ v + v + 1 ] ); } void upd( int v, int tl, int tr, int pos, int x ) { if ( tl > pos || tr < pos ) return; if ( tl == tr ) { t[ v ] = x; return; } int mid = ( tl + tr ) / 2; upd( v + v, tl, mid, pos, x ); upd( v + v + 1, mid + 1, tr, pos, x ); t[ v ] = lca( t[ v + v ], t[ v + v + 1 ] ); } void gett( int v, int tl, int tr, int l, int r ) { if ( tl > r || tr < l ) return; if ( tl >= l && tr <= r ) { if ( !num ) num = t[ v ]; else num = lca( num, t[ v ] ); return; } int mid = ( tl + tr ) / 2; gett( v + v, tl, mid ,l ,r ); gett( v + v + 1, mid + 1, tr, l, r ); } set <pair<int, int> > st[ 200001 ]; 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 ++ ) { cin >> x >> y; v[ x ].push_back( y ); v[ y ].push_back( x ); } for ( int i = 1; i <= m; i ++ ) { cin >> a[ i ]; } dfs( 1 ); int L, R; for ( int i = 1; i < m; i ++ ) { st[ lca( a[ i ], a[ i + 1 ] ) ].insert( { i, i + 1 } ); st[ a[ i ] ].insert( { i, i } ); } st[ a[ m ] ].insert( { m, m } ); while ( q -- ) { cin >> type >> l >> r; if ( type == 1 ) { if ( l < m ) { st[ lca( a[ l ], a[ l + 1 ] ) ].erase( { l, l + 1 } ); st[ lca( r, a[ l + 1 ] ) ].insert( { l, l + 1 } ); } if ( l > 1 ) { st[ lca( a[ l ], a[ l - 1 ] ) ].erase( { l - 1, l } ); st[ lca( a[ l - 1 ], r ) ].insert( { l - 1, l } ); } st[ a[ l ] ].erase( { l, l } ); a[ l ] = r; st[ r ].insert( { l, l } ); } else { cin >> x; auto it = st[ x ].lower_bound( { l, l } ); if ( it != st[ x ].end() && it->second <= r ) cout << it->first << " " << it->second << "\n"; else cout << "-1 -1\n"; } } } /* CX 1 1 3 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 */

컴파일 시 표준 에러 (stderr) 메시지

treearray.cpp: In function 'int main()':
treearray.cpp:135:6: warning: unused variable 'L' [-Wunused-variable]
  135 |  int L, R;
      |      ^
treearray.cpp:135:9: warning: unused variable 'R' [-Wunused-variable]
  135 |  int L, R;
      |         ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...