Submission #1050527

#TimeUsernameProblemLanguageResultExecution timeMemory
1050527LucaIlieFire (BOI24_fire)C++17
100 / 100
1357 ms356216 KiB
#include <bits/stdc++.h> #define int long long using namespace std; struct interval { int l, r; }; struct maxpos { int max, pos; bool operator < ( const maxpos &x ) const { return max < x.max; } }; const int MAX_N = 2e5; const int MAX_VAL = 4 * MAX_N; const int MAX_LOG_N = 17; const int MAX_LOG_VAL = MAX_LOG_N + 2; int nxt[MAX_LOG_N + 2][2 * MAX_N]; interval v[2 * MAX_N]; maxpos maxR[MAX_LOG_VAL + 1][MAX_VAL]; map<int, int> normal; signed main() { int n, m; cin >> n >> m; for ( int i = 0; i < n; i++ ) { int l, r; cin >> l >> r; if ( l > r ) r += m; v[i] = { l, r }; v[i + n] = { l + m, r + m }; normal[l] = 0; normal[l + m] = 0; normal[r] = 0; normal[r + m] = 0; } n *= 2; int val = 0; for ( auto x: normal ) normal[x.first] = val++; //for ( int i = 0; i < n; i++ ) // printf( "%d %d\n", v[i].l, v[i].r ); for ( int i = 0; i < n; i++ ) maxR[0][normal[v[i].l]] = max( maxR[0][normal[v[i].l]], { v[i].r, i } ); for ( int l = 1; (1 << l) <= val; l++ ) { for ( int i = 0; i <= val - (1 << l); i++ ) maxR[l][i] = max( maxR[l - 1][i], maxR[l - 1][i + (1 << (l - 1))] ); } for ( int i = 0; i < n; i++ ) { int l = log2( normal[v[i].r] - normal[v[i].l] ); nxt[0][i] = max( maxR[l][normal[v[i].l]], maxR[l][normal[v[i].r] - (1 << l) + 1] ).pos; } for ( int l = 1; (1 << l) <= n; l++ ) { for ( int i = 0; i < n; i++ ) nxt[l][i] = nxt[l - 1][nxt[l - 1][i]]; } int minLen = n + 1; for ( int i = 0; i < n; i++ ) { int len = 1, p = i; for ( int l = log2( n ); l >= 0; l-- ) { if ( v[nxt[l][p]].r < v[i].l + m ) { p = nxt[l][p]; len += (1 << l); } } if ( v[p].r < v[i].l + m ) { p = nxt[0][p]; len++; } if ( v[p].r >= v[i].l + m ) minLen = min( minLen, len ); } cout << (minLen == n + 1 ? -1 : minLen); return 0; }
#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...