Submission #423587

#TimeUsernameProblemLanguageResultExecution timeMemory
423587JvThunderAutobahn (COI21_autobahn)C++14
100 / 100
818 ms52452 KiB
#include <bits/stdc++.h> #define pb push_back #define mp make_pair #define fir first #define sec second typedef long long ll; using namespace std; int n,k,z; multiset<pair<pair<int,int>,int>> s; vector<pair<pair<int,int>,int>> val; void solve() { cin >> n >> k >> z; set<int> all; for(int i=0;i<n;i++) { int l,t,r; cin >> l >> t >> r; s.insert({{l,l+t-1},0}); s.insert({{l+t,r},1}); all.insert(l); all.insert(max(1,l+t-z)); all.insert(l+t-1); all.insert(l+t); all.insert(max(1,r-z+1)); all.insert(r); all.insert(r+1); } priority_queue<pair<int,int>> pq; int cnt = 0; auto itr = s.begin(); int prv = 0; for(auto x:all) { if(pq.size()>=k) val.pb({{prv,x-1},cnt}); prv = x; while(itr!=s.end() && (*itr).fir.fir<=x) { if((*itr).sec==1) cnt++; pq.push({-(*itr).fir.sec,(*itr).sec}); itr++; } while(!pq.empty() && -pq.top().fir<x) { if(pq.top().sec==1) cnt--; pq.pop(); } } ll sum = 0; ll mxsum = 0; int ptr2 = -1; for(int ptr=0;ptr<val.size();ptr++) { while(ptr2+1<val.size() && val[ptr2+1].fir.sec<val[ptr].fir.fir+z) { ptr2++; sum += (ll)val[ptr2].sec*(val[ptr2].fir.sec-val[ptr2].fir.fir+1); } mxsum = max(mxsum,sum); sum -= (ll)val[ptr].sec*(val[ptr].fir.sec-val[ptr].fir.fir+1); } cout << mxsum << endl; return; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int tc=1; //cin>>tc; for(int i=1;i<=tc;i++) solve(); return 0; }

Compilation message (stderr)

autobahn.cpp: In function 'void solve()':
autobahn.cpp:38:21: warning: comparison of integer expressions of different signedness: 'std::priority_queue<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   38 |         if(pq.size()>=k) val.pb({{prv,x-1},cnt});
      |            ~~~~~~~~~^~~
autobahn.cpp:58:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |     for(int ptr=0;ptr<val.size();ptr++)
      |                   ~~~^~~~~~~~~~~
autobahn.cpp:60:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |         while(ptr2+1<val.size() && val[ptr2+1].fir.sec<val[ptr].fir.fir+z)
      |               ~~~~~~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...