Submission #1002795

#	Time	Username	Problem	Language	Result	Execution time	Memory
1002795		Cabralbonzao	Autobahn (COI21_autobahn)	C++17	20 / 100	1 ms	604 KiB

autobahn

#include<bits/stdc++.h>
using namespace std;

#define N 200010
#define M 2000000020
#define pb push_back

typedef long long ll;
typedef pair<ll,ll> pll;

vector<pll>range;
set<ll>tests;
vector<ll>test;

struct event{
ll l,r,s;
};

vector<event>soma;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    ll n,k,x,i=0,l,t,r,pos,val,cur=0,s=0,ans=0,sz,curl,curr,resp=0,ql,qr;
 
    cin >> n >> k >> x;
    while(i<n)
    {
        cin >> l >> t >> r;
        range.pb({l,1});
        range.pb({r+1,-1});
        range.pb({l+t,2});
        range.pb({r+1,-2});
        i++;
    }
    sort(range.begin(),range.end());
    i=0;
    n*=4;
    range.pb({-1,0});
    while(i<n)
    {
        pos=range[i].first;
        while(range[i].first==pos)
        {
            val=range[i].second;
            if(val==1)
                cur++;
            if(val==-1)
                cur--;
            if(val==2)
                s++;
            if(val==-2)
                s--;
            i++;
        }
        if(cur>=k)
        {
            r=range[i].first-1;
            soma.pb({pos,r,s});
            tests.insert(pos);
            tests.insert(max(1LL,r-x+1));
        }
    }
    for(auto t : tests)
        test.pb(t);
    curl=1;
    curr=1;
    ql=0;
    qr=0;
    t=0;
    cur=0;
    soma.pb({0,M,0});
    sz=tests.size();
    while(t<sz)
    {
        l=test[t]-1;
        r=test[t]+x-1;
        while(curr<r)
        {
            if(soma[qr].r>r)
            {
                resp+=(r-max(soma[qr].l-1,curr))*soma[qr].s;
                curr=r;
                break;
            }
            resp+=(soma[qr].r-max(soma[qr].l-1,curr))*soma[qr].s;
            curr=soma[qr].r;
            qr++;
        }
        while(curl<l)
        {
            if(soma[ql].r>l)
            {
                resp-=max(0LL,(l-max(soma[ql].l-1,curl))*soma[ql].s);
                curl=l;
                break;
            }
            resp-=max(0LL,(soma[ql].r-max(soma[ql].l-1,curl))*soma[ql].s);
            curl=soma[ql].r;
            ql++;
        }
        ans=max(ans,resp);
        t++;
    }
    cout << ans << endl;

    return 0;
}

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