Submission #462023

#TimeUsernameProblemLanguageResultExecution timeMemory
462023JasiekstrzAutobahn (COI21_autobahn)C++17
100 / 100
89 ms6604 KiB
#include<bits/stdc++.h> #define fi first #define se second using namespace std; const int N=1e5; vector<pair<int,int>> ev; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n,k,x; cin>>n>>k>>x; for(int i=1;i<=n;i++) { int l,r,t; cin>>l>>t>>r; if(l+t<=r) { ev.emplace_back(l+t,0); ev.emplace_back(r+1,1); } ev.emplace_back(l,2); ev.emplace_back(r+1,3); } sort(ev.begin(),ev.end()); int l=-x,r=0; int cntl=0,cntr=0; int opl=0,opr=0; long long ans=0,tmp=0; for(int i=0,j=0;i<ev.size();) { if(j>=ev.size() || ev[i].fi-l<ev[j].fi-r) { long long d=ev[i].fi-l; if(opr>=k) tmp+=d*cntr; if(opl>=k) tmp-=d*cntl; l+=d; r+=d; if(ev[i].se==0) cntl++; else if(ev[i].se==1) cntl--; else if(ev[i].se==2) opl++; else opl--; i++; } else { long long d=ev[j].fi-r; if(opr>=k) tmp+=d*cntr; if(opl>=k) tmp-=d*cntl; l+=d; r+=d; if(ev[j].se==0) cntr++; else if(ev[j].se==1) cntr--; else if(ev[j].se==2) opr++; else opr--; j++; } //cerr<<l<<" "<<r<<" "<<tmp<<"\n"; ans=max(ans,tmp); } cout<<ans<<"\n"; return 0; }

Compilation message (stderr)

autobahn.cpp: In function 'int main()':
autobahn.cpp:31:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |  for(int i=0,j=0;i<ev.size();)
      |                  ~^~~~~~~~~~
autobahn.cpp:33:7: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |   if(j>=ev.size() || ev[i].fi-l<ev[j].fi-r)
      |      ~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...