Submission #1019923

#	Time	Username	Problem	Language	Result	Execution time	Memory
1019923		ttamx	Overtaking (IOI23_overtaking)	C++17	39 / 100	3565 ms	8388 KiB

overtaking

#include <bits/stdc++.h>
#include "overtaking.h"

using namespace std;

using ll = long long;

const int N=1005;
const ll LIM=1e18;

int n,m,x;
ll s[N],dp[N][N];
vector<pair<int,ll>> bus;

struct SegTree{
    struct Node;
    using Ptr = Node*;
    struct Tag{
        ll lz;
        bool is_lz;
        Tag():lz(0),is_lz(false){}
        Tag(ll x):lz(x),is_lz(true){}
    };
    struct Node{
        ll val;
        Tag lz;
        Ptr l,r;
        Node(ll _val):val(_val),lz(),l(),r(){}
    };
    Ptr root;
    ll offset;
    SegTree():root(new Node(LIM)),offset(0){}
    void apply(ll l,ll r,Ptr &t,Tag v){
        if(!t)t=new Node(r);
        if(v.is_lz){
            t->val=v.lz;
            t->lz=v;
        }
    }
    void push(ll l,ll m,ll r,Ptr &t){
        apply(l,m,t->l,t->lz);
        apply(m+1,r,t->r,t->lz);
        t->lz=Tag();
    }
    void pull(Ptr &t){
        t->val=max(t->l->val,t->r->val);
    }
    void update(ll l,ll r,Ptr &t,ll x,ll y,const Tag &v){
        if(y<l||r<x)return;
        if(x<=l&&r<=y)return apply(l,r,t,v);
        ll m=(l+r)/2;
        push(l,m,r,t);
        update(l,m,t->l,x,y,v);
        update(m+1,r,t->r,x,y,v);
    }
    void update(ll x,ll y,ll v){
        update(0,LIM,root,x,y,Tag(v-offset));
    }
    ll query(ll l,ll r,Ptr &t,ll x){
        if(l==r)return t->val;
        ll m=(l+r)/2;
        push(l,m,r,t);
        return x<=m?query(l,m,t->l,x):query(m+1,r,t->r,x);
    }
    ll query(ll x){
        return query(0,LIM,root,x)+offset;
    }
    void add_all(ll x){
        offset+=x;
    }
    template<class F>
    ll find_first(ll l,ll r,Ptr &t,ll x,ll y,const F &f){
        if(y<l||r<x||!f(t->val+offset))return LIM+1;
        if(l==r)return l;
        ll m=(l+r)/2;
        push(l,m,r,t);
        ll res=find_first(l,m,t->l,x,y,f);
        if(res>LIM)res=find_first(m+1,r,t->r,x,y,f);
        return res;
    }
    template<class F>
    ll find_first(ll x,ll y,const F &f){
        return find_first(0,LIM,root,x,y,f);
    }
}seg;

void init(int _l,int _n,vector<ll> _t,vector<int> _w,int _x,int _m,vector<int> _s){
    n=_n,m=_m-1,x=_x;
    for(int i=0;i<=m;i++)s[i]=_s[i];
    for(int i=0;i<n;i++)bus.emplace_back(_w[i],_t[i]);
    sort(bus.rbegin(),bus.rend());
    while(!bus.empty()&&bus.back().first<=x)bus.pop_back();
    n=bus.size();
    for(int i=0;i<n;i++)dp[0][i]=bus[i].second;
    for(int i=0;i<m;i++){
        ll dist=s[i+1]-s[i];
        vector<pair<ll,ll>> exp,real;
        for(int j=0;j<n;j++){
            ll w=bus[j].first;
            dp[i+1][j]=dp[i][j]+w*dist;
            exp.emplace_back(dp[i][j],dp[i+1][j]);
        }
        sort(exp.begin(),exp.end());
        for(auto [l,r]:exp){
            if(!real.empty()){
                if(real.back().first==l)real.back().second=r;
                else if(real.back().second<r)real.emplace_back(l,r);
            }else{
                real.emplace_back(l,r);
            }
        }
        auto calc=[&](ll x){
            auto it=lower_bound(real.begin(),real.end(),pair<ll,ll>(x,0));
            if(it!=real.begin())return prev(it)->second;
            return 0LL;
        };
        for(int j=0;j<n;j++){
            dp[i+1][j]=max(dp[i+1][j],calc(dp[i][j]));
        }
        // reverse(real.begin(),real.end());
        // vector<tuple<ll,ll,ll>> upd;
        // ll dif=x*dist;
        // ll last=LIM;
        // for(auto [l,r]:real){
        //     ll l2=seg.find_first(0,last,[&](ll v){return v>l;});
        //     ll r2=min(seg.find_first(0,last,[&](ll v){return v+dif>r;})-1,last);
        //     if(l2<=r2){
        //         upd.emplace_back(l2,r2,r);
        //         last=l2-1;
        //     }
        // }
        // seg.add_all(dif);
        // for(auto [l,r,v]:upd)seg.update(l,r,v);
    }
}

ll arrival_time(ll y){
    for(int i=0;i<n;i++)dp[0][i]=bus[i].second;
    for(int i=0;i<m;i++){
        ll dist=s[i+1]-s[i];
        vector<pair<ll,ll>> exp,real;
        for(int j=0;j<n;j++){
            ll w=bus[j].first;
            dp[i+1][j]=dp[i][j]+w*dist;
            exp.emplace_back(dp[i][j],dp[i+1][j]);
        }
        sort(exp.begin(),exp.end());
        for(auto [l,r]:exp){
            if(!real.empty()){
                if(real.back().first==l)real.back().second=r;
                else if(real.back().second<r)real.emplace_back(l,r);
            }else{
                real.emplace_back(l,r);
            }
        }
        auto calc=[&](ll x){
            auto it=lower_bound(real.begin(),real.end(),pair<ll,ll>(x,0));
            if(it!=real.begin())return prev(it)->second;
            return 0LL;
        };
        for(int j=0;j<n;j++){
            dp[i+1][j]=max(dp[i+1][j],calc(dp[i][j]));
        }
        y=max(y+x*dist,calc(y));
    }
    return y;
}

• Subtask 0: 0 / 0
• Subtask 1: 9 / 9
• Subtask 2: 10 / 10
• Subtask 3: 20 / 20
• Subtask 4: 0 / 26
• Subtask 5: 0 / 35