Submission #1002739

#	Time	Username	Problem	Language	Result	Execution time	Memory
1002739		Cabralbonzao	Autobahn (COI21_autobahn)	C++17	50 / 100	1034 ms	160372 KiB

autobahn

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

#define N 200010
#define pb push_back

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

map<ll,ll>st;
map<ll,ll>lazy;
vector<pll>range;
set<ll>tests;
vector<ll>test;

void LAZY(ll i,ll l,ll r)
{
    if(lazy.find(i)==lazy.end())
        return;
    ll val=lazy[i],nxt=(i<<1);
    lazy.erase(i);
    st[i]+=(r-l+1)*val;
    if(l==r)
        return;
    lazy[nxt]+=val;
    lazy[nxt+1]+=val;
    return;
}

void update(ll i,ll l,ll r,ll L,ll R,ll val)
{
    if(l>R || L>r)
        return;
    if(L<=l && r<=R)
    {
        lazy[i]+=val;
        return;
    }
    ll nxt=(i<<1),mid=((l+r)>>1);
    update(nxt,l,mid,L,R,val);
    update(nxt+1,mid+1,r,L,R,val);
    st[i]+=(min(r,R)-max(l,L)+1)*val;
    return;
}

void BIGUPD(ll i,ll l,ll r)
{
    LAZY(i,l,r);
    if(l==r)
        return;
    ll nxt=(i<<1),mid=((l+r)>>1);
    BIGUPD(nxt,l,mid);
    BIGUPD(nxt+1,mid+1,r);
    return;
}

ll query(ll i,ll l,ll r,ll L,ll R)
{
    if(l>R || L>r)
        return 0LL;
    if(L<=l && r<=R)
        return st[i];
    ll nxt=(i<<1),mid=((l+r)>>1);
    return query(nxt,l,mid,L,R)+
           query(nxt+1,mid+1,r,L,R);
}

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,mx=0;
 
    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});
        mx=max(mx,r+1);
        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;
            update(1,1,mx,pos,r,s);
            tests.insert(pos);
            tests.insert(max(1LL,r-x+1));
        }
    }
    BIGUPD(1,1,mx);
    for(auto t : tests)
        test.pb(t);
    for(auto l : test)
    {
        ans=max(ans,query(1,1,mx,l,l+x-1));
    }
    cout << ans << endl;

    return 0;
}

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