Submission #543857

#	Time	Username	Problem	Language	Result	Execution time	Memory
543857		1BeeNY1	Autobahn (COI21_autobahn)	C++17	100 / 100	169 ms	9424 KiB

autobahn

#include <bits/stdc++.h>
 
using namespace std;
 
long long n,k,x,nr,tr,pr,numbers;
long long ans=0;
long long suma[300005];
 
struct curse
{
    int st,dr;
    long long cost;
} v[300005];
 
struct evenimente
{
    int st,dr;
} ev[300005];
 
struct intervale
{
    int st,dr;
    long long cost;
} need[300005];
 
pair<int,int>conteaza[300005];
pair<int,int>pozitii[300005];
 
int main()
{
    cin>>n>>k>>x;
 
    for(int i=1; i<=n; i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
 
        if(a+b-1<c)
        {
            nr++;
            pozitii[nr]= {a+b,1};
            nr++;
            pozitii[nr]= {c+1,-1};
        }
        conteaza[i]= {a,1};
        conteaza[n+i]= {c+1,-1};
    }
 
    ///intervalele unde se aplica costul
    sort(conteaza+1,conteaza+2*n+1);
    int ct=0;
 
    for(int i=1; i<=2*n; i++)
    {
        int val=conteaza[i].first;
        ct+=conteaza[i].second;
 
        while(i+1<=2*n&&conteaza[i+1].first==val)
        {
            i++;
            ct+=conteaza[i].second;
        }
 
        if(i==2*n) break;
        if(ct>=k)
        {
            if(tr&&ev[tr].dr==val-1) ev[tr].dr=conteaza[i+1].first-1;
            else
            {
                tr++;
                ev[tr].st=val;
                ev[tr].dr=conteaza[i+1].first-1;
            }
        }
    }
 
    ///intervalele cu cost
    sort(pozitii+1,pozitii+nr+1);
    ct=0;
 
    for(int i=1; i<=nr; i++)
    {
        int val=pozitii[i].first;
        ct+=pozitii[i].second;
 
        while(i+1<=nr&&pozitii[i+1].first==val)
        {
            i++;
            ct+=pozitii[i].second;
        }
 
        if(i==nr) break;
 
        if(ct!=0)
        {
            pr++;
            v[pr].st=val;
            v[pr].dr=pozitii[i+1].first-1;
            v[pr].cost=ct;
        }
    }
 
    if(tr==0||pr==0)
    {
        cout<<'0'<<'\n';
        return 0;
    }
 
    ///creez intervalele disjuncte prin care sa pot cauta binar raspunsul
    int poz=0;
    for(int i=1; i<=pr; i++)
    {
        while(poz+1<=tr&&v[i].st>ev[poz].dr) poz++;
        if(ev[poz].dr<v[i].st) break;
 
        if(ev[poz].st<=v[i].st&&v[i].dr<=ev[poz].dr)
        {
            numbers++;
            need[numbers].st=v[i].st;
            need[numbers].dr=v[i].dr;
            need[numbers].cost=v[i].cost;
 
            continue;
        }
 
        if(ev[poz].st<v[i].st)
        {
            numbers++;
            need[numbers].st=v[i].st;
            need[numbers].dr=ev[poz].dr;
            need[numbers].cost=v[i].cost;
            poz++;
        }
 
        if(poz>tr) break;
 
        while( poz<=tr&&v[i].st<ev[poz].st&&ev[poz].dr<=v[i].dr )
        {
            numbers++;
            need[numbers].st=ev[poz].st;
            need[numbers].dr=ev[poz].dr;
            need[numbers].cost=v[i].cost;
            poz++;
        }
        
        if(poz>tr) break;
 
        if(ev[poz].st<=v[i].dr)
        {
            numbers++;
            need[numbers].st=ev[poz].st;
            need[numbers].dr=v[i].dr;
            need[numbers].cost=v[i].cost;
            continue;
        }
    }
 
    for(int i=1; i<=numbers; i++) suma[i]=suma[i-1]+1LL*(need[i].dr-need[i].st+1)*need[i].cost;
 
    ///plec de la stanga la dreapta
    for(int i=1; i<=numbers; i++)
    {
        int rasp=i-1,st=i,dr=numbers,mid;
 
        while(st<=dr)
        {
            mid=(st+dr)/2;
 
            if(need[mid].dr<=need[i].st+x-1) rasp=mid,st=mid+1;
            else dr=mid-1;
        }
 
        long long ss=0;
        if(rasp!=i-1) ss=suma[rasp]-suma[i-1];
        rasp++;
        if(rasp<=numbers&&need[rasp].st<=need[i].st+x-1) ss+=1LL*(need[i].st+x-need[rasp].st)*need[rasp].cost;
 
        ans=max(ans,ss);
    }
    ///plec de la dreapta la stanga
    for(int i=1; i<=numbers; i++)
    {
        int rasp=i+1,st=1,dr=i,mid;
 
        while(st<=dr)
        {
            mid=(st+dr)/2;
 
            if(need[mid].st>=need[i].dr-x+1) rasp=mid,dr=mid-1;
            else st=mid+1;
        }
 
        long long ss=0;
        if(rasp!=i+1) ss=suma[i]-suma[rasp-1];
 
        rasp--;
 
        if(rasp>=1&&need[rasp].dr>=need[i].dr-x+1) ss+=1LL*(need[rasp].dr-need[i].dr+x)*need[rasp].cost;
 
        ans=max(ans,ss);
    }
 
    cout<<ans;
 
    return 0;
}

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