Submission #1165401

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165401		lighton	Train (APIO24_train)	C++20	100 / 100	489 ms	345276 KiB

train

#include "train.h"
#include<bits/stdc++.h>
#define pb push_back
#define all(v) v.begin(),v.end()
#define forf(i,s,e) for(int i = s; i<=e; i++)
#define forb(i,s,e) for(int i = s; i>=e; i--)
#define idx(i,v) lower_bound(all(v),i)-v.begin()
#define comp(v) v.erase(unique(all(v)),v.end())
#define fs first
#define se second
#define sz(v) (int)v.size()
#define SPACE << " " <<
#define LINE << "\n"
using namespace std;
typedef long long ll;
ll inf = 4e18;

int N,M,W,S;
vector<ll> CS;
vector<int> tx;
struct Node{
    int v,l,r;
} def = {0,0,0};
struct PST{
    int rt[400001];
    vector<int> root = {0};
    vector<Node> node = {def};
    void update(int now, int prv, int s, int e, int f, int x){
        if(s==e){node[now].v = node[prv].v+x; return;}
        int m = s+e>>1;
        if(f<=m){
            node[now].l = node.size(); node.push_back(def);
            node[now].r = node[prv].r;
            update(node[now].l,node[prv].l,s,m,f,x);
        }
        else{
            node[now].r = node.size(); node.push_back(def);
            node[now].l = node[prv].l;
            update(node[now].r,node[prv].r,m+1,e,f,x);
        }
        node[now].v = node[node[now].l].v + node[node[now].r].v;
    }
    int query(int now , int prv, int s, int e,int l ,int r){
        if(l<=s && e<=r) return node[now].v-node[prv].v;
        if(r<s || l>e) return 0;
        int m = s+e>>1;
        return query(node[now].l,node[prv].l,s,m,l,r)+query(node[now].r,node[prv].r,m+1,e,l,r);
    }
    int bin(int now, int prv, int s, int e, ll k){
        if(s==e){
            if(k <= node[now].v - node[prv].v) return s;
            else return s+1;
        }
        int tmp = node[node[now].l].v - node[node[prv].l].v;
        int m =s+e>>1;
        if(k <= tmp) return bin(node[now].l, node[prv].l,s,m,k);
        else return bin(node[now].r, node[prv].r, m+1,e,k-tmp);
    }
} pst;

struct Line{
    ll idx,s,st, c;
    ll eval(ll e) const{
        if(e == s) return c;
        return c+CS[idx]*pst.query(pst.rt[e-1], pst.rt[s], 1,S, 1,e-1);
    }
};
int cross(Line x, Line y){
    if(x.eval(y.s) > y.eval(y.s)) return y.s;
    ll k = (y.c - x.c) / CS[y.idx] + 1;
    return pst.bin(pst.rt[y.s], pst.rt[x.s], 1, S, k)+1;
}

vector<int> pos[400001];
deque<Line> Q[400001];
vector<Line> ins[400001];
vector<array<ll,4> > upd[400001];

long long solve(int N, int M, int W, std::vector<int> T, std::vector<int> X, std::vector<int> Y,
                std::vector<int> A, std::vector<int> B, std::vector<int> C, std::vector<int> L,
                std::vector<int> R) {
    ::N=N, ::M=M, ::W=W;
    forf(i,0,N-1) CS.pb(T[i]);
    forf(i,0,M-1) tx.pb(A[i]), tx.pb(B[i]); forf(i,0,W-1) tx.pb(L[i]), tx.pb(R[i]);
    sort(all(tx)), comp(tx); S = sz(tx);
    forf(i,0,M-1) A[i] = idx(A[i],tx)+1, B[i] = idx(B[i],tx)+1; forf(i,0,W-1) L[i] = idx(L[i],tx)+1, R[i] = idx(R[i],tx)+1, pos[L[i]].pb(R[i]);
    forf(i,0,M-1) upd[A[i]].pb({X[i],Y[i],B[i],C[i]});

    forf(i,1,S){
        for(auto j : pos[i]){
            pst.root.pb(sz(pst.node)), pst.node.pb(def);
            pst.update(pst.root.back(),pst.root[sz(pst.root)-2],1,S,j,1);
        }
        pst.rt[i] = pst.root.back();
    }

    Q[0].pb({0,0,0,0}); forf(i,1,N-1) Q[i].pb({0,0,0,inf});
    forf(t,1,S){
        for(auto now : ins[t]){
            int idx = now.idx;
            while(sz(Q[idx]) >= 2 && Q[idx].back().st >= cross(Q[idx].back(),now)) Q[idx].pop_back();
            now.st = cross(Q[idx].back(),now);
            Q[idx].pb(now);
        }

        for(auto [s,e,et,c] : upd[t]){
            while(sz(Q[s]) >= 2 && Q[s][1].st <= t) Q[s].pop_front();
            ll cst = Q[s].front().eval(t) + c;
            ins[et].pb({e,et,et,cst});
        }
    }

    while(sz(Q[N-1]) >= 2 && Q[N-1][1].st <= S+1) Q[N-1].pop_front();
    if(Q[N-1].front().eval(S+1) >= inf) return -1;
    return Q[N-1].front().eval(S+1);
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 30 / 30
• Subtask 4: 60 / 60