제출 #1002787

#제출 시각아이디문제언어결과실행 시간메모리
1002787LoboAutobahn (COI21_autobahn)C++17
100 / 100
322 ms45360 KiB
#include<bits/stdc++.h> using namespace std; #define int long long #define pb push_back #define mp make_pair #define fr first #define sc second #define all(x) x.begin(),x.end() int32_t main() { // #ifndef ONLINE_JUDGE // freopen("in.in","r",stdin); // freopen("out.out","w",stdout); // #endif int n,k,x; map<int,vector<pair<pair<int,int>,int>>> eve; cin >> n >> k >> x; for(int i = 0; i < n; i++) { int l,r,t; cin >> l >> t >> r; eve[l].pb(mp(mp(l,+1),0)); eve[r+1].pb(mp(mp(r+1,-1),0)); if(l+t < r+1) { eve[l+t].pb(mp(mp(l+t,+1),1)); eve[r+1].pb(mp(mp(r+1,-1),1)); } } int ant = 0; vector<pair<pair<int,int>,int>> extras; int people = 0; int extra = 0; for(auto X : eve) { int tempo = X.fr; if(people >= k) { // ant,tempo-1 extras.pb(mp(mp(ant,tempo-1),extra)); } ant = tempo; for(auto XX : eve[tempo]) { int val = XX.fr.sc; if(XX.sc == 0) { people+= val; } else { extra+= val; } } } int ans = 0; int sumtot = 0; // nao pego nem le nem re inteiros por padrao int re = 0; for(int le = 0; le < extras.size(); le++) { // cout << final-extras[le].fr.fr << " " << final-extras[le].fr.sc << " " << extras[le].sc << endl; // cout << " " << le << " " << extras[le].fr.fr << " " << " " << extras[le].fr.sc << " " << extras[le].sc << endl; int l = extras[le].fr.fr; int r = l+x-1; while(re+1 < extras.size() && r >= extras[re+1].fr.fr) { sumtot+= (extras[re].fr.sc-extras[re].fr.fr+1)*extras[re].sc; re++; } if(le == re) { ans = max(ans, (min(r,extras[re].fr.sc)-extras[re].fr.fr+1)*extras[re].sc); // cout << ans << " " << sumtot << endl; re++; } else { ans = max(ans, sumtot+(min(r,extras[re].fr.sc)-extras[re].fr.fr+1)*extras[re].sc); // cout << ans << " " << sumtot << " " << le << " " << re << endl; sumtot-= (extras[le].fr.sc-extras[le].fr.fr+1)*extras[le].sc; } } // cout << ans << endl; int final = 1e9+1; for(int i = 0; i < extras.size(); i++) { extras[i].fr = mp(final-extras[i].fr.sc,final-extras[i].fr.fr); } reverse(all(extras)); sumtot = 0; re = 0; for(int le = 0; le < extras.size(); le++) { // cout << final-extras[le].fr.fr << " " << final-extras[le].fr.sc << " " << extras[le].sc << endl; // cout << " " << le << " " << extras[le].fr.fr << " " << " " << extras[le].fr.sc << " " << extras[le].sc << endl; int l = extras[le].fr.fr; int r = l+x-1; while(re+1 < extras.size() && r >= extras[re+1].fr.fr) { sumtot+= (extras[re].fr.sc-extras[re].fr.fr+1)*extras[re].sc; re++; } if(le == re) { ans = max(ans, (min(r,extras[re].fr.sc)-extras[re].fr.fr+1)*extras[re].sc); // cout << ans << " " << sumtot << endl; re++; } else { ans = max(ans, sumtot+(min(r,extras[re].fr.sc)-extras[re].fr.fr+1)*extras[re].sc); // cout << ans << " " << sumtot << " " << le << " " << re << endl; sumtot-= (extras[le].fr.sc-extras[le].fr.fr+1)*extras[le].sc; } } cout << ans << endl; }

컴파일 시 표준 에러 (stderr) 메시지

autobahn.cpp: In function 'int32_t main()':
autobahn.cpp:56:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |  for(int le = 0; le < extras.size(); le++) {
      |                  ~~~^~~~~~~~~~~~~~~
autobahn.cpp:62:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |   while(re+1 < extras.size() && r >= extras[re+1].fr.fr) {
      |         ~~~~~^~~~~~~~~~~~~~~
autobahn.cpp:81:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |  for(int i = 0; i < extras.size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~
autobahn.cpp:87:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |  for(int le = 0; le < extras.size(); le++) {
      |                  ~~~^~~~~~~~~~~~~~~
autobahn.cpp:93:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |   while(re+1 < extras.size() && r >= extras[re+1].fr.fr) {
      |         ~~~~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...