oj.uz

Submission #1002739

# Submission time Handle Problem Language Result Execution time Memory
1002739 2024-06-19T18:55:38 Z Cabralbonzao Autobahn (COI21_autobahn) C++17
50 / 100
 1000 ms 160372 KB 
#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 2 ms 604 KB Output is correct
13 Correct 1 ms 604 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 1 ms 604 KB Output is correct
17 Correct 1 ms 604 KB Output is correct
18 Correct 1 ms 600 KB Output is correct
19 Correct 2 ms 604 KB Output is correct
20 Correct 1 ms 600 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 2 ms 604 KB Output is correct
13 Correct 1 ms 604 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 1 ms 604 KB Output is correct
17 Correct 1 ms 604 KB Output is correct
18 Correct 1 ms 600 KB Output is correct
19 Correct 2 ms 604 KB Output is correct
20 Correct 1 ms 600 KB Output is correct
21 Execution timed out 1034 ms 160372 KB Time limit exceeded
22 Halted 0 ms 0 KB -