Submission #1066815

#	Time	Username	Problem	Language	Result	Execution time	Memory
1066815		LittleOrange	Overtaking (IOI23_overtaking)	C++17	100 / 100	2734 ms	1361236 KiB

overtaking

#include "overtaking.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll big = 2e18;
ll n,m,l,x;
vector<ll> w,s;
vector<vector<ll>> t,e;
vector<vector<pair<ll,ll>>> vs;
vector<pair<ll,ll>> all;
struct node{
    ll l,r,m,v;
    node *lp, *rp;
    node(ll a, ll b):l(a),r(b),m((l+r)>>1),v(0),lp(nullptr),rp(nullptr){}
    node* L(){
        if(lp==nullptr) lp = new node(l,m);
        return lp;
    }
    node* R(){
        if(rp==nullptr) rp = new node(m+1,r);
        return rp;
    }
    void pull(){
        if(lp) v = max(v,lp->v);
        if(rp) v = max(v,rp->v);
    }
    void upd(ll i, ll x){
        if (l==r) v = max(v,x);
        else{
            if (i<=m) L()->upd(i,x);
            else R()->upd(i,x);
            pull();
        }
    }
    ll qry(ll ql, ll qr){
        if(ql<=l&&r<=qr) return v;
        else{
            ll ret = -big;
            if (ql<=m&&lp) ret = max(ret,lp->qry(ql,qr));
            if (qr>m&&rp) ret = max(ret,rp->qry(ql,qr));
            return ret;
        }
    }
};
node* tree;
void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S)
{
    n = N;
    m = M;
    l = L;
    x = X;
    w.assign(W.begin(),W.end());
    s.assign(S.begin(),S.end());
    tree = new node(-big,big);
    t.resize(n+1,vector<ll>(m));
    for(ll i = 0;i<n;i++) t[i][0] = T[i];
    e = t;
    vs.emplace_back();
    for(ll j = 1;j<m;j++){
        vector<pair<ll,ll>> v;
        for(ll i = 0;i<n;i++){
            t[i][j] = e[i][j] = t[i][j-1]+w[i]*(s[j]-s[j-1]);
            v.push_back({t[i][j-1],e[i][j]});
        }
        sort(v.begin(),v.end());
        for(ll i = 1;i<n;i++){
            v[i].second = max(v[i].second,v[i-1].second);
        }
        for(ll i = 0;i<n;i++){
            auto it = lower_bound(v.begin(),v.end(),make_pair(t[i][j-1],0ll));
            if (it==v.begin()) continue;
            --it;
            t[i][j] = max(t[i][j],(*it).second);
        }
        vs.push_back(v);
    }
    for(auto [a,b] : vs.back()){
        tree->upd(a+x*(s[m-1]-s[m-2]),b);
        all.push_back({a+x*(s[m-1]-s[m-2]),b});
        //all.insert({a+x*(s[m-1]-s[m-2]),b});
    }
    for(ll j = m-2;j>0;j--){
        for(auto [a,b] : vs[j]){
            ll nw = b+x*(s[m-1]-s[j]);
            ll g = tree->qry(0,nw-1);
            b = max(nw,g);
            tree->upd(a+x*(s[m-1]-s[j-1]),b);
            all.push_back({a+x*(s[m-1]-s[j-1]),b});
            //all.insert({a+x*(s[m-1]-s[j-1]),b});
        }
    }
    sort(all.begin(),all.end());
    for(ll i = 1;i<all.size();i++){
        all[i].second = max(all[i].second,all[i-1].second);
    }
    /*for(ll j = 1;j<m;j++){
        for(auto [a,b] : lvl[j]){
            //cout << j << " " << a << " " << b << "\n";
            //cout << a-x*(S[j-1]-S[0]) << " " << b << "\n";
            all.push_back({a-x*(S[j-1]-S[0]),b});
        }
    }
    sort(all.begin(),all.end());
    for(ll i = 1;i<all.size();i++){
        all[i].second = max(all[i].second,all[i-1].second);
    }*/
    //cout << "e:\n";
    //for(ll i = 0;i<n;i++) for(ll j = 0;j<m;j++) cout << e[i][j] << " \n"[j+1==m];
    //cout << "t:\n";
    //for(ll i = 0;i<n;i++) for(ll j = 0;j<m;j++) cout << t[i][j] << " \n"[j+1==m];
    //for(auto [a,b] : all){
    //    cout << a << " " << b << "\n";
    //}
}
 
long long arrival_time(long long Y)
{
    /*for(ll j = 1;j<m;j++){
        auto it = lower_bound(vs[j].begin(),vs[j].end(),make_pair(Y,0ll));
        ll nxt = Y+x*(s[j]-s[j-1]);
        if (it!=vs[j].begin()){
            --it;
            nxt = max(nxt,(*it).second);
        }
        Y = nxt;
    }*/
    ll ans = Y+x*l;
    auto it = lower_bound(all.begin(),all.end(),make_pair(ans,0ll));
    if (it!=all.begin()){
        --it;
        ans = max(ans,(*it).second);
    }
    return ans;
}

Compilation message (stderr)

overtaking.cpp: In function 'void init(int, int, std::vector<long long int>, std::vector<int>, int, int, std::vector<int>)':
overtaking.cpp:93:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |     for(ll i = 1;i<all.size();i++){
      |                  ~^~~~~~~~~~~

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