Submission #543822

#	Time	Username	Problem	Language	Result	Execution time	Memory
543822		1BeeNY1	Autobahn (COI21_autobahn)	C++17	0 / 100	2 ms	340 KiB

autobahn

#include <bits/stdc++.h>

using namespace std;

int n,k,x,nr,tr,pr,numbers;
long long ans=0;
long long suma[200005];

struct curse
{
    int st,dr,cost;
} v[200005];

struct evenimente
{
    int st,dr;
} ev[200005];

struct intervale
{
    int st,dr,cost;
} need[200005];

pair<int,int>conteaza[200005];
pair<int,int>pozitii[200005];

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;
    }

    int poz=0;

    for(int i=1; i<=pr; i++)
    {
        while(poz+1<=nr&&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>nr) break;

        while( poz<=nr&&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(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: 0 / 20
• Subtask 2: 0 / 30
• Subtask 3: 0 / 50