Submission #467208

#	Time	Username	Problem	Language	Result	Execution time	Memory
467208		julian33	Autobahn (COI21_autobahn)	C++14	50 / 100	107 ms	25356 KiB

autobahn

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {
    cerr<<vars<<" = ";
    string delim="";
    (...,(cerr<<delim<<values,delim=", "));
    cerr<<"\n";
}
#else
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {}
#endif

#define pb push_back
#define sz(x) (int)(x.size())
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<typename T> inline void maxa(T& a,T b){a=max(a,b);}
template<typename T> inline void mina(T& a,T b){a=min(a,b);} 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int mxN=2e5+5; //make sure this is right
const int mod=1e9+7;

struct evt{
    int p,ppl,cst;
    bool operator<(const evt &o) const{
        return p<o.p;
    }
};
ll total=0;
ll pay=0;
int nxt[mxN];

int main(){
    cin.sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    #ifdef LOCAL
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    #endif

    int n,k,x; cin>>n>>k>>x;
    vector<evt> off,ac;
    for(int i=0;i<n;i++){
        int l,t,r; cin>>l>>t>>r;
        off.pb({l,1,0});
        off.pb({r+1,-1,0});
        if(l+t<=r){
            off.pb({l+t,0,1});
            off.pb({r+1,0,-1});
        }
    }
    sort(off.begin(),off.end());
    ac.pb(off[0]);
    for(int i=1;i<sz(off);i++){
        if(off[i].p==ac.back().p){
            ac.back().ppl+=off[i].ppl;
            ac.back().cst+=off[i].cst;
        } else{
            assert(off[i].p-1>=ac.back().p);
            nxt[sz(ac)-1]=off[i].p-1;
            ac.pb(off[i]);
        }
    }
    ll ans=0;
    ll cur=0;
    queue<pair<pii,ll>> q;
    int i=0;
    for(auto &u:ac){
        total+=u.ppl;
        pay+=u.cst;
        if(total<k){
            i++;
            continue;
        }
        deb(u.p,nxt[i],total,pay,cur);
        while(sz(q) && q.front().first.second+x<=u.p){
            cur-=q.front().second*(q.front().first.second-q.front().first.first+1);
            q.pop();
        }
        if(sz(q) && q.front().first.first+x<=u.p){
            ll overlap=q.front().second*(u.p-x-q.front().first.first+1);
            maxa(ans,cur-overlap+pay);
        } else{
            deb(cur,pay);
            maxa(ans,cur+pay);
        }
        int pre=u.p;
        u.p=nxt[i];
        while(sz(q) && q.front().first.second+x<=u.p){
            cur-=q.front().second*(q.front().first.second-q.front().first.first+1);
            q.pop();
        }
        ll amt=(ll)(u.p-pre+1)*pay;
        if(sz(q) && q.front().first.first+x<=u.p){
            ll overlap=q.front().second*(u.p-x-q.front().first.first+1);
            maxa(ans,cur-overlap+amt);
        } else{
            deb(cur,amt);
            maxa(ans,cur+amt);
        }
        q.push({{pre,u.p},pay});
        cur+=amt;
        i++;
    }
    cout<<ans<<"\n";
}

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