Submission #719488

#TimeUsernameProblemLanguageResultExecution timeMemory
719488vinnipuh01Event Hopping (BOI22_events)C++17
100 / 100
422 ms58844 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> #define int long long #define sqrt sqrtl using namespace std; const long long oo = 1000000000000000000; long long sum, ans = 0, mx = 0, mn = 1000000000, num, pos; /* ViHHiPuh (( `'-""``""-'` )) )-__-_.._-__-( / --- (o _ o) --- \ \ .-* ( .0. ) *-. / _'-. ,_ '=' _, .-'_ / `;#'#'# - #'#'#;` \ \_)) -----'#'----- ((_/ # --------- # '# ------- ------ #' /..-'# ------- #'-.\ _\...-\'# -- #'/-.../_ ((____)- '#' -(____)) cout << fixed << setprecision(6) << x; freopen ( "sum.in", "r", stdin ) */ int n, q, x, y, l[ 100001 ], r[ 200001 ]; int mp[ 100001 ]; int t[ 800001 ]; struct Node { int mn, i; Node operator + ( Node a ) { Node c; if ( mn < a.mn ) c.mn = mn, c.i = i; else c = a; return c; } } tt[ 800001 ], an; vector <pair<pair<int, int> , int> > vv; vector <int> v[ 100001 ]; int pr[ 20 ][ 100001 ]; int tin[ 100001 ], tout[ 100001 ], tmr; int used[ 100001 ]; vector <int> g; map <int, int> mpp; set <pair<int, int> > st; void upd1( int v, int tl, int tr, int pos ) { if ( tl > pos || tr < pos ) return; if ( tl == tr ) { if ( tt[ v ].mn > an.mn ) tt[ v ] = an; return; } int mid = ( tl + tr ) / 2; upd1( v + v, tl, mid, pos ); upd1( v + v + 1, mid + 1, tr, pos ); tt[ v ] = tt[ v + v ] + tt[ v + v + 1 ]; } void gett1( int v, int tl, int tr, int l, int r ) { if ( tl > r || tr < l ) return; if ( tl >= l && tr <= r ) { an = an + tt[ v ]; return; } int mid = ( tl + tr ) / 2; gett1( v + v, tl, mid, l, r ) ; gett1( v + v + 1, mid + 1, tr, l, r ); } void build( int v, int tl, int tr ) { t[ v ] = oo; tt[ v ].mn = oo; if ( tl == tr ) return; int mid = ( tl + tr ) / 2; build( v + v, tl, mid ); build( v + v + 1, mid + 1, tr ); } void upd( int v, int tl, int tr, int pos, int x ) { if ( tl > pos || tr < pos ) return; if ( tl == tr ) { t[ v ] = min( 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 ] = min( 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 ) { num = min( 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 ); } void dfs( int u, int pr ) { ::pr[ 0 ][ u ] = pr; used[ u] = 1; tin[ u ] = ++tmr; for ( int i = 1; i < 20; i ++ ) ::pr[ i ][ u ] = ::pr[ i - 1 ][ ::pr[ i - 1 ][ u ] ]; for ( auto to : v[ u ] ) { if ( to != pr ) dfs( to, u ); } tout[ u ] = tmr; } bool ok( int a, int b ) { return ( tin[ a ] <= tin[ b ] && tout[ a ] >= tout[ b ] ); } int bin( int a, int b ) { for ( int i = 19; i >= 0; i -- ) { if ( r[ b ] < l[ pr[ i ][ a ] ] ) { a = pr[ i ][ a ]; ans += ( 1 << i ); } } return a; } main () { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> q; build( 1, 1, n + n ); for ( int i = 1; i <= n; i ++ ) { cin >> l[ i ] >> r[ i ]; g.push_back( l[ i ] ); g.push_back( r[ i ] ); } sort( g.begin(), g.end() ); for ( auto i : g ) { if ( !mpp[ i ] ) { mpp[ i ] = ++num; } } for ( int i = 1; i <= n; i ++ ) { l[ i ] = mpp[ l[ i ] ]; r[ i ] = mpp[ r[ i ] ]; upd( 1, 1, n + n, r[ i ], l[ i ] ); } for ( int i = 1; i <= n; i ++ ) { vv.push_back( { make_pair( r[ i ], l[ i ] ), i } ); } sort( vv.begin(), vv.end() ); for ( int i = 0; i < n; i ++ ) { mp[ vv[ i ].second ] = i + 1; l[ i + 1 ] = vv[ i ].first.second; r[ i + 1 ] = vv[ i ].first.first; } for ( int i = 1; i <= n; i ++ ) { an.mn = oo; gett1( 1, 1, n + n, l[ i ], r[ i ] ); if ( an.mn < l[ i ] ) { v[ an.i ].push_back( i ); } an = { l[ i ], i }; upd1( 1, 1, n + n, r[ i ] ); } for ( int i = 1; i <= n; i ++ ) { if ( !used[ i ] ) { dfs( i, i ); } } int x, L, R; while ( q -- ) { cin >> x >> y; x = mp[ x ]; y = mp[ y ]; if ( x == y ) { cout << "0\n"; continue; } if ( l[ y ] <= r[ x ] && r[ x ] <= r[ y ] ) { cout << "1\n"; continue; } if ( y < x ) { cout << "impossible\n"; continue; } ans = 2; y = bin( y, x ); num = oo; gett( 1, 1, n + n, l[ y ], r[ y ] ); if ( num <= r[ x ] ) cout << ans << "\n"; else cout << "impossible\n"; } }

Compilation message (stderr)

events.cpp:161:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  161 | main () {
      | ^~~~
events.cpp: In function 'int main()':
events.cpp:205:9: warning: unused variable 'L' [-Wunused-variable]
  205 |  int x, L, R;
      |         ^
events.cpp:205:12: warning: unused variable 'R' [-Wunused-variable]
  205 |  int x, 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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...