Submission #1261680

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261680		nerrrmin	Train (APIO24_train)	C++20	0 / 100	67 ms	26624 KiB

train

#include "train.h"
#include <bits/stdc++.h>
#define pb push_back
#include <vector>
using namespace std;
const long long maxn = 2e5 + 10;
long long n, m, w;
struct way
{
    long long from, to, tstart, tend, cost, index;
    way(long long _from, long long _to, long long _tstart, long long _tend, long long _cost, long long _index)
    {
        from = _from;
        to = _to;
        cost = _cost;
        tstart = _tstart;
        tend = _tend;
        index = _index;
    }
};

bool cmp(way w1, way w2)
{
    if(w1.from != w2.from)return(w1.from < w2.from);
    if(w1.tstart != w2.tstart)return (w1.tstart < w2.tstart);
    return (w1.index < w2.index);
}

bool cmp2(way w1, way w2)
{
    if(w1.tstart != w2.tstart)return (w1.tstart < w2.tstart);
    return (w1.index < w2.index);
}
vector < way > g, u;
long long pos[maxn], start[maxn], last[maxn];
long long x[maxn], y[maxn], a[maxn], b[maxn], c[maxn];

long long dp[maxn];

long long t[maxn * 4], lazy[maxn * 4];
void build(long long i, long long l, long long r)
{
    lazy[i] = 1e17;
    if(l == r)
    {
        t[i] = dp[l];
        return;
    }
    long long mid = (l + r)/2;
    build(2*i, l, mid);
    build(2*i+1, mid+1, r);
    t[i] = min(t[2*i], t[2*i+1]);
}
long long ql, qr, uval;
void push_lazy(long long i, long long l, long long r)
{
    assert(i < 5e5);
    t[i] = min(t[i], lazy[i]);
    if(l != r)
    {
        lazy[2*i] = min(lazy[2*i], lazy[i]);
        lazy[2*i+1] = min(lazy[2*i+1], lazy[i]);
    }
    lazy[i] = 1e17;
}
void update(long long i, long long l, long long r)
{
    assert(i < 5e5);
    if(qr < ql)return;
    push_lazy(i, l, r);
    if(ql > r || qr < l)return;
    if(ql <= l && r <= qr)
    {
        lazy[i] = uval;
        push_lazy(i, l, r);
        return;
    }
    long long mid = (l + r)/2;
    update(2*i, l, mid);
    update(2*i+1, mid+1, r);
    t[i] = min(t[2*i], t[2*i+1]);
}
long long qpos;
long long query(long long i, long long l, long long r)
{
    assert(i < 5e5);
    push_lazy(i, l ,r);
    if(l == r)return t[i];
    long long mid = (l + r)/2;
    if(qpos <= mid)return query(2*i, l, mid);
    else return query(2*i+1, mid+1, r);

}

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;
    for (long long i = 0; i < m; ++ i)
    {
        x[i] = X[i];
        y[i] = Y[i];
        a[i] = A[i];
        b[i] = B[i];
        c[i] = C[i];
        g.pb(way(x[i], y[i], a[i], b[i], c[i], i));
        u.pb(way(x[i], y[i], a[i], b[i], c[i], i));
    }
  //  cout << "mark 1 " << endl;
    sort(g.begin(), g.end(), cmp);
    sort(u.begin(), u.end(), cmp2);
    long long j = 0;
    long long prefrom = -1;
    memset(start, -1 ,sizeof(start));
    memset(last, -1, sizeof(last));
    for (auto &[from, to, st, fi, c, i]: g)
    {
        if(from != prefrom)
        {
            start[from] = j;
        }
        pos[i] = j;
        last[from] = j;
        prefrom = from;
        j ++;
    }
    for (int i = 0; i < m; ++ i)
        assert(pos[i] < m);
   // cout << "mark 2" << endl;
    for (long long i = 0; i < m; ++ i)
    {
        if(x[i] == 0)dp[pos[i]] = 0;
        else dp[pos[i]] = 1e17;
    }
    build(1, 0, m-1);
    long long ans = 1e17;
   // cout << "mark 3" << endl;
    for (auto &[from, to, st, fi, c, i]: u)
    {
       // cout << i << endl;
        qpos = pos[i];
        dp[pos[i]] = query(1, 0, m-1);
      //  cout << dp[pos[i]] << endl;
      //  cout << "*" << endl;
        long long bestcost = dp[pos[i]] + c;
      //  cout << to << " " << bestcost << endl;
        if(to == n-1)ans = min(ans, bestcost);
        if(start[to] == -1)continue;
        long long lt = start[to], rt = last[to], mid, anss = last[to] + 1; /// pyrvoto po golqmo ot fi
        while(lt <= rt)
        {
            mid = (lt + rt)/2;
            if(g[mid].tstart >= fi)
            {
                anss = mid;
                rt = mid - 1;
            }
            else lt = mid + 1;
        }
        //cout << "**" << endl;
        if(anss == last[to] + 1)continue;
        ql = anss;
        qr = last[to];
        assert(ql < qr);
        uval = bestcost;
        update(1, 0, m-1);
        //cout << "*** " << endl;
    }
    if(ans == 1e17)return -1;
    return ans;
}

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