Submission #1261457

#TimeUsernameProblemLanguageResultExecution timeMemory
1261457kikitop1ggFire (BOI24_fire)C++17
40 / 100
2093 ms58712 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define vi vector<ll> #define vvi vector<vector<ll>> #define vs vector<string> #define vc vector<char> #define vb vector<bool> #define vp vector<pair<ll, ll>> #define vpp vector<pair<ll, pair<ll, ll>>> #define pp pair<ll, ll> #define qi queue<ll> #define qp queue<pp> #define pqi priority_queue<ll> #define pqp priority_queue<pp> #define mi map<ll, ll> #define mpi map<pp, ll> #define mip map<ll, pp> #define mp map<pp, pp> #define mb map<ll, bool> #define si set<ll> #define sp set<pp> #define sc set<char> #define mod 1000000007 #define inf INT_MAX #define all(x) (x).begin(), (x).end() ll get_max(ll l, ll r, ll k, ll a, ll b, vi& tree) { if(r < a || b < l) return -1; if(a <= l && r <= b) return tree[k]; ll d = (l + r) / 2; return max(get_max(l, d, 2 * k, a, b, tree), get_max(d + 1, r, 2 * k + 1, a, b, tree)); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); ll n, m; cin >> n >> m; vp a(n); si times; for(int i = 0; i < n; i++) { cin >> a[i].first >> a[i].second; if(a[i].first > a[i].second) a[i].second += m; times.insert(a[i].first); times.insert(a[i].second); } vi coor2; mi coor; for(auto time : times) { coor[time] = coor2.size(); coor2.push_back(time); } ll size = pow(2, ceil(log2(int(times.size())))); vi tree(size * 2, -1); for(int i = 0; i < n; i++) { ll start = coor[a[i].first]; ll end = coor[a[i].second]; tree[start + size] = end; } for(int i = size - 1; i > 0; i--) { tree[i] = max(tree[i * 2], tree[i * 2 + 1]); } ll ans = inf; for(auto[start, end] : a) { ll l = coor[start], r = coor[end]; ll cur = 1; while(true) { ll mx = get_max(0, size - 1, 1, l, r, tree); if(mx <= r) { cur = inf; break; } ll real = coor2[mx]; cur++; if(real >= start + m) break; l = r; r = mx; } ans = min(ans, cur); } if(ans == inf) ans = -1; cout << ans << '\n'; return 0; } /* 4 100 11 30 0 9 9 0 4 5 2 */
#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...