Submission #434913

#TimeUsernameProblemLanguageResultExecution timeMemory
434913dqhungdlAutobahn (COI21_autobahn)C++17
0 / 100
2 ms296 KiB
#include <bits/stdc++.h> #define int long long using namespace std; typedef pair<int,int> ii; int N,K,X; vector<ii> events,overtime,charge; int32_t main() { #ifdef ACM freopen("input","r",stdin); #endif cin>>N>>K>>X; int l,t,r; for(int i=0;i<N;i++) { cin>>l>>t>>r; if(l+t<=r) { overtime.push_back({l+t,1}); overtime.push_back({r+1,-1}); } events.push_back({l,1}); events.push_back({r+1,-1}); } sort(events.begin(),events.end()); int people=0,pivot; for(ii event:events) { people+=event.second; if(event.second==1&&people==K) pivot=event.first; else if(event.second==-1&&people==K-1) { overtime.push_back({pivot,2}); overtime.push_back({event.first,-2}); } } sort(overtime.begin(),overtime.end()); //for(ii tmp:overtime) // cerr<<tmp.first<<' '<<tmp.second<<'\n'; int numOvertime=0; bool overload=false; for(ii event:overtime) { if(abs(event.second)==1) numOvertime+=event.second; else overload=(event.second==2); if(overload) { if(charge.size()>0&&charge.back().first==event.first) charge.back().second=numOvertime; else charge.push_back({event.first,numOvertime}); } else if(charge.size()>0&&charge.back().first==event.first) charge.back().second=0; else charge.push_back({event.first,0}); } //for(ii tmp:charge) // cerr<<tmp.first<<' '<<tmp.second<<'\n'; vector<int> S(charge.size()); for(int i=0;i<charge.size()-1;i++) { S[i]=(charge[i+1].first-charge[i].first)*charge[i].second; if(i>0) S[i]+=S[i-1]; } int cur=0,rs=0; for(int i=0;i<charge.size()-1;i++) { while(cur<charge.size()-1&&charge[cur+1].first<=charge[i].first+X-1) cur++; int sum=0; if(cur>0) sum=S[cur-1]-(i==0?0:S[i-1]); sum+=(charge[i].first+X-charge[cur].first)*charge[cur].second; rs=max(rs,sum); } cur=0; for(int i=0;i<charge.size()-1;i++) { while(cur<i&&charge[cur].first+X<charge[i+1].first) cur++; int sum=S[i]-S[cur]; if(cur>0) sum+=(charge[cur].first-charge[i+1].first+X)*charge[cur-1].second; rs=max(rs,sum); } cout<<rs; }

Compilation message (stderr)

autobahn.cpp: In function 'int32_t main()':
autobahn.cpp:59:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |  for(int i=0;i<charge.size()-1;i++) {
      |              ~^~~~~~~~~~~~~~~~
autobahn.cpp:65:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |  for(int i=0;i<charge.size()-1;i++) {
      |              ~^~~~~~~~~~~~~~~~
autobahn.cpp:66:12: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |   while(cur<charge.size()-1&&charge[cur+1].first<=charge[i].first+X-1)
      |         ~~~^~~~~~~~~~~~~~~~
autobahn.cpp:75:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |  for(int i=0;i<charge.size()-1;i++) {
      |              ~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...