Submission #1279554

#TimeUsernameProblemLanguageResultExecution timeMemory
1279554ducksaysquackFire (BOI24_fire)C++20
100 / 100
248 ms89656 KiB
#include <bits/stdc++.h> #define int long long #define f first #define s second using namespace std; signed main() { int n, m; cin >> n >> m; vector<pair<int,int>> v(n); for(int i=0;i<n;i++) {cin >> v[i].f >> v[i].s; if(v[i].s < v[i].f) v[i].s += m;} sort(begin(v),end(v)); for(int i=0;i<n;i++) v.push_back({v[i].f+m,v[i].s+m}); for(int i=0;i<n;i++) v.push_back({v[i].f+2*m,v[i].s+2*m}); int ans = 1e9; vector<pair<int,int>> t(3*n); vector<vector<pair<int,int>>> c(n,vector<pair<int,int>>(20)); t[0] = {v[0].s,0}; for(int i=1;i<3*n;i++) if(t[i-1].f < v[i].s) t[i].f = v[i].s, t[i].s = i%n; else t[i] = t[i-1]; for(int i=0;i<n;i++) { auto p = t[upper_bound(v.begin(),v.end(),make_pair(v[i+n].s,(int)1e18))-begin(v)-1]; if(p.f <= v[i+n].s) {cout << -1; return 0;} else c[i][0].f = p.s, c[i][0].s = (v[p.s].s-v[i].s+m)%m; } for(int i=1;i<20;i++) for(int j=0;j<n;j++) c[j][i].f = c[c[j][i-1].f][i-1].f, c[j][i].s = c[j][i-1].s+c[c[j][i-1].f][i-1].s; for(int i=0;i<n;i++) { int a = 1, b = i, d = v[i].s-v[i].f; for(int j=19;j+1;j--) if(c[b][j].s+d < m) a += (1<<j), d += c[b][j].s, b = c[b][j].f; ans = min(ans, a+1); } cout << ans << '\n'; }
#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...