Submission #1052283

#TimeUsernameProblemLanguageResultExecution timeMemory
1052283VMaksimoski008Autobahn (COI21_autobahn)C++17
100 / 100
115 ms12988 KiB
#include <bits/stdc++.h> //#define int long long using namespace std; using ll = long long; using pii = pair<int, int>; using pll = pair<ll, ll>; const int mod = 1e9 + 7; const int LOG = 20; const int maxn = 1e5 + 5; signed main() { int n, k, x; ll ans = 0; cin >> n >> k >> x; vector<array<int, 2> > v; for(int i=0; i<n; i++) { int l, t, r; cin >> l >> t >> r; v.push_back({ l, 0 }); v.push_back({ l + t, 1 }); v.push_back({ r + 1, 2 }); v.push_back({ l + x, 3 }); v.push_back({ l + t + x, 4 }); v.push_back({ r + x + 1, 5 }); } sort(v.begin(), v.end()); ll prv=-1, st=0, ed=0, curr=0, chargeSt=0, chargeEd=0; for(auto &[t, type] : v) { ll coef = 0; if(st >= k) coef += chargeSt; if(ed >= k) coef -= chargeEd; curr += coef * (t - prv); if(type == 0) st++; if(type == 1) chargeSt++; if(type == 2) st--, chargeSt--; if(type == 3) ed++; if(type == 4) chargeEd++; if(type == 5) ed--, chargeEd--; ans = max(ans, curr); prv = t; } cout << ans << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...