Submission #467208

#TimeUsernameProblemLanguageResultExecution timeMemory
467208julian33Autobahn (COI21_autobahn)C++14
50 / 100
107 ms25356 KiB
#include <bits/stdc++.h> using namespace std; #ifdef LOCAL #define deb(...) logger(#__VA_ARGS__, __VA_ARGS__) template<typename ...Args> void logger(string vars, Args&&... values) { cerr<<vars<<" = "; string delim=""; (...,(cerr<<delim<<values,delim=", ")); cerr<<"\n"; } #else #define deb(...) logger(#__VA_ARGS__, __VA_ARGS__) template<typename ...Args> void logger(string vars, Args&&... values) {} #endif #define pb push_back #define sz(x) (int)(x.size()) typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll; template<typename T> inline void maxa(T& a,T b){a=max(a,b);} template<typename T> inline void mina(T& a,T b){a=min(a,b);} mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const int mxN=2e5+5; //make sure this is right const int mod=1e9+7; struct evt{ int p,ppl,cst; bool operator<(const evt &o) const{ return p<o.p; } }; ll total=0; ll pay=0; int nxt[mxN]; int main(){ cin.sync_with_stdio(0); cin.tie(0); cout.tie(0); #ifdef LOCAL freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); #endif int n,k,x; cin>>n>>k>>x; vector<evt> off,ac; for(int i=0;i<n;i++){ int l,t,r; cin>>l>>t>>r; off.pb({l,1,0}); off.pb({r+1,-1,0}); if(l+t<=r){ off.pb({l+t,0,1}); off.pb({r+1,0,-1}); } } sort(off.begin(),off.end()); ac.pb(off[0]); for(int i=1;i<sz(off);i++){ if(off[i].p==ac.back().p){ ac.back().ppl+=off[i].ppl; ac.back().cst+=off[i].cst; } else{ assert(off[i].p-1>=ac.back().p); nxt[sz(ac)-1]=off[i].p-1; ac.pb(off[i]); } } ll ans=0; ll cur=0; queue<pair<pii,ll>> q; int i=0; for(auto &u:ac){ total+=u.ppl; pay+=u.cst; if(total<k){ i++; continue; } deb(u.p,nxt[i],total,pay,cur); while(sz(q) && q.front().first.second+x<=u.p){ cur-=q.front().second*(q.front().first.second-q.front().first.first+1); q.pop(); } if(sz(q) && q.front().first.first+x<=u.p){ ll overlap=q.front().second*(u.p-x-q.front().first.first+1); maxa(ans,cur-overlap+pay); } else{ deb(cur,pay); maxa(ans,cur+pay); } int pre=u.p; u.p=nxt[i]; while(sz(q) && q.front().first.second+x<=u.p){ cur-=q.front().second*(q.front().first.second-q.front().first.first+1); q.pop(); } ll amt=(ll)(u.p-pre+1)*pay; if(sz(q) && q.front().first.first+x<=u.p){ ll overlap=q.front().second*(u.p-x-q.front().first.first+1); maxa(ans,cur-overlap+amt); } else{ deb(cur,amt); maxa(ans,cur+amt); } q.push({{pre,u.p},pay}); cur+=amt; i++; } cout<<ans<<"\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...