Submission #990949

#	Time	Username	Problem	Language	Result	Execution time	Memory
990949		alexdd	Autobahn (COI21_autobahn)	C++17	100 / 100	461 ms	65836 KiB

autobahn

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,k,lun,cate;
vector<pair<int,int>> v,v2;
map<int,int> mp,nrm;
int inv[400005];
int mars[400005],mars2[400005];
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>k>>lun;
    int le,ri,t;
    for(int i=1;i<=n;i++)
    {
        cin>>le>>t>>ri;
        //for(int j=le;j<=ri;j++)mp[j]++;
        v2.push_back({le,ri});
        mp[le]++;
        mp[ri]++;
        mp[ri+1]++;
        le+=t;
        if(ri>=le)
        {
            v.push_back({le,ri});
            mp[le]++;
        }
    }
    for(auto it:mp)
    {
        nrm[it.first]=++cate;
        inv[cate]=it.first;
    }
    for(auto x:v)
    {
        mars[nrm[x.first]]++;
        mars[nrm[x.second+1]]--;
    }
    for(auto x:v2)
    {
        mars2[nrm[x.first]]++;
        mars2[nrm[x.second+1]]--;
    }
    for(int i=1;i<=cate;i++)
    {
        mars2[i]+=mars2[i-1];
        mars[i]+=mars[i-1];
        //cout<<i<<"  "<<mars2[i]<<" "<<mars[i]<<" mars\n";
        //cout<<i<<" "<<inv[i]<<" inv\n";
    }
    for(int i=1;i<=cate;i++)
        if(mars2[i]<k)
            mars[i]=0;
    int poz=1,sum=0,mxm=0;
    inv[cate+1]=inv[cate]+1;
    for(int i=1;i<cate;i++)
    {
        sum += mars[i]*(inv[i+1]-inv[i]);
        while(inv[i+1]-inv[poz+1] >= lun)
        {
            sum -= mars[poz]*(inv[poz+1]-inv[poz]);
            poz++;
        }
        mxm = max(mxm, sum - mars[poz]*((inv[i+1]-inv[poz])-lun));
    }
    cout<<mxm;
    return 0;
}

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