Submission #1116102

#TimeUsernameProblemLanguageResultExecution timeMemory
1116102SalihSahinAutobahn (COI21_autobahn)C++14
100 / 100
199 ms38532 KiB
#include <bits/stdc++.h> #define pb push_back #define int long long using namespace std; const int inf = 1e16; const int N = 1e3 + 5; int32_t main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n, k, x; cin>>n>>k>>x; vector<array<int, 3> > upd; set<int> vis; for(int i = 0; i < n; i++){ int l, t, r; cin>>l>>t>>r; if(r - l + 1 > t){ upd.pb({l, i, 0}); upd.pb({l+t, i, 1}); upd.pb({r+1, i, 2}); vis.insert(l); vis.insert(r+1); vis.insert(l+t); } else{ upd.pb({l, i, 0}); upd.pb({r+1, i, 2}); vis.insert(l); vis.insert(r+1); } } sort(upd.begin(), upd.end()); vector<int> col(n); // 0 yok, 1 iceride, 2 oduyor vector<array<int, 3> > odeme; int act = 0, ode = 0, ind = 0; for(auto i: vis){ while(ind < upd.size() && upd[ind][0] <= i){ if(upd[ind][2] == 0){ act++; col[upd[ind][1]] = 1; } else if(upd[ind][2] == 1){ col[upd[ind][1]] = 2; ode++; } else{ if(col[upd[ind][1]] == 2) ode--; act--; col[upd[ind][1]] = 0; } ind++; } if(act >= k){ odeme.pb({i, upd[ind][0]-1, ode}); } } if(!odeme.size()){ cout<<0<<endl; return 0; } int hh = 0, ans = 0; ind = 0; for(int i = 0; i < odeme.size(); i++){ int l = odeme[i][0]; while(ind < odeme.size() && odeme[ind][1] <= l + x - 1){ hh += odeme[ind][2] * (odeme[ind][1] - odeme[ind][0] + 1); ind++; } int add = 0; if(ind < odeme.size() && l + x - 1 >= odeme[ind][0]){ add = odeme[ind][2] * (l + x - 1 - odeme[ind][0] + 1); } ans = max(ans, hh + add); hh -= odeme[i][2] * (odeme[i][1] - odeme[i][0] + 1); } ind = odeme.size()-1; hh = 0; for(int i = odeme.size()-1; i >= 0; i--){ int r = odeme[i][1]; while(ind >= 0 && odeme[ind][0] >= r - x + 1){ hh += odeme[ind][2] * (odeme[ind][1] - odeme[ind][0] + 1); ind--; } int add = 0; if(ind >= 0 && r - x + 1 <= odeme[ind][1]){ add = odeme[ind][2] * (odeme[ind][1] - (r - x + 1) + 1); } ans = max(ans, hh + add); hh -= odeme[i][2] * (odeme[i][1] - odeme[i][0] + 1); } cout<<ans<<endl; return 0; }

Compilation message (stderr)

autobahn.cpp: In function 'int32_t main()':
autobahn.cpp:43:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |       while(ind < upd.size() && upd[ind][0] <= i){
      |             ~~~~^~~~~~~~~~~~
autobahn.cpp:73:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |    for(int i = 0; i < odeme.size(); i++){
      |                   ~~^~~~~~~~~~~~~~
autobahn.cpp:75:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |       while(ind < odeme.size() && odeme[ind][1] <= l + x - 1){
      |             ~~~~^~~~~~~~~~~~~~
autobahn.cpp:80:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |       if(ind < odeme.size() && l + x - 1 >= odeme[ind][0]){
      |          ~~~~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...