Submission #419308

#	Time	Username	Problem	Language	Result	Execution time	Memory
419308		Runtime_error_	Autobahn (COI21_autobahn)	C++14	100 / 100	229 ms	17800 KiB

autobahn

#include <bits/stdc++.h>
#define ll long long
#define mid (l+r)/2
#define pb push_back
#define mp make_pair
#define all(v) v.begin(),v.end()
using namespace std;
const ll inf = 1e5+9,MX = 2e9+9;
ll n,k,x,ans;
vector<pair<ll,ll> > events;

struct Range{
    ll l,r,cost;
    ll add(){
        return sz()*cost;
    }
    ll sz(){
        return r-l+1;
    }
};
vector<Range> ranges;
vector<ll> presum;
int main(){
    cin>>n>>k>>x;
    for(ll i=1;i<=n;i++){
        ll l,r,t;
        cin>>l>>t>>r;
        events.pb(mp(l,1));
        t = min(t,r-l+1);
        events.pb(mp(l+t,2));
        events.pb(mp(r+1,3));
    }

    sort(all(events));
    ranges.pb({0,0,0});
    presum.pb(0);
    ll cnt = 0,charge = 0;
    for(ll i=0;i<events.size();){
        ll j = i;
        while(j<events.size() && events[j].first == events[i].first){
            if(events[j].second == 1)
                cnt++;
            else if(events[j].second == 2)
                charge++;
            else
                cnt--,charge--;
            j++;
        }
        if(cnt>=k)
            ranges.push_back({events[i].first,(j<events.size()?events[j].first:MX)-1,charge});
        i = j;
    }

    ll sum = 0;
    for(ll i=1;i<ranges.size();i++)
        presum.pb(presum.back() + ranges[i].add());

    for(ll i=1;i<ranges.size();i++){
        ll cur = ranges[i].l + x-1;
        ll l = i,r = ranges.size();
        while(r-l>1){
            if(ranges[mid].l > cur)
                r = mid;
        else
            l = mid;
        }
        ll p1 = presum[l-1] - presum[i-1];
        ll p2 =  ranges[l].cost*min(ranges[l].sz(),(cur-ranges[l].l+1) );
        ans = max(ans, p1+p2);

        cur = ranges[i].r-x+1,l =0,r = i;
        while(r-l>1){
            if(ranges[mid].r< cur)
                l = mid;
            else
                r = mid;
        }
        p1 = presum[i] - presum[r];
        p2 = ranges[r].cost*min(ranges[r].sz(),ranges[r].r-cur+1);
        ans = max(ans,p1+p2);
    }

    cout<<ans<<endl;
}

Compilation message (stderr)

autobahn.cpp: In function 'int main()':
autobahn.cpp:39:17: 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]
   39 |     for(ll i=0;i<events.size();){
      |                ~^~~~~~~~~~~~~~
autobahn.cpp:41:16: 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]
   41 |         while(j<events.size() && events[j].first == events[i].first){
      |               ~^~~~~~~~~~~~~~
autobahn.cpp:51:49: 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]
   51 |             ranges.push_back({events[i].first,(j<events.size()?events[j].first:MX)-1,charge});
      |                                                ~^~~~~~~~~~~~~~
autobahn.cpp:56:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<Range>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     for(ll i=1;i<ranges.size();i++)
      |                ~^~~~~~~~~~~~~~
autobahn.cpp:59:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<Range>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for(ll i=1;i<ranges.size();i++){
      |                ~^~~~~~~~~~~~~~
autobahn.cpp:55:8: warning: unused variable 'sum' [-Wunused-variable]
   55 |     ll sum = 0;
      |        ^~~

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 50 / 50