Submission #1065792

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065792		alexdd	Train (APIO24_train)	C++17	10 / 100	1073 ms	56892 KiB

train

#include "train.h"
#include <bits/stdc++.h>
using namespace std;
const long long LIM = 0;
const long long INF = 1e14;
struct train
{
    int from,to;
    int tin,tout;
    int cost;
};
bool cmp_trains(train x, train y)
{
    return x.tin < y.tin;
}
bool cmp_meals(pair<int,int> x, pair<int,int> y)
{
    return x.second < y.second;
}
vector<train> trains;
bool cmp_tout(int x, int y)
{
    return trains[x].tout < trains[y].tout;
}
vector<pair<int,int>> meals;
long long dp[100005];
vector<int> meal_cost;
vector<int> train_ends[100005];
bool isbig[100005];
int cntin[100005],cntout[100005];
vector<int> big_nodes;
long long prec[100005];
long long calced[100005],inplus[100005];
vector<int> ids_tout;
int poz_meals=-1,cate;

int aib[400005];
int qry_aib(int poz)
{
    int aux=0;
    for(int i=poz;i<=cate;i+=(i&(-i)))
        aux += aib[i];
    return aux;
}
void upd_aib(int poz, int newv)
{
    for(int i=poz;i>0;i-=(i&(-i)))
        aib[i] += newv;
}


void solve_small(int i)
{
    for(int j:train_ends[trains[i].from])
    {
        if(trains[j].tout <= trains[i].tin)
        {
            if(dp[j] < dp[i]) dp[i] = min(dp[i], dp[j] + (long long)qry_aib(trains[j].tout+1)*meal_cost[trains[i].from] + trains[i].cost);
        }
    }
}

vector<pair<int,int>> aint[100005];///{val,lazy}
void build(int nod, int st, int dr, int c)
{
    aint[c][nod] = {INF,0};
    if(st==dr)
        return;
    int mij=(st+dr)/2;
    build(nod*2,st,mij,c);
    build(nod*2+1,mij+1,dr,c);
}
void propagate(int nod, int c)
{
    if(!aint[c][nod].second)
        return;
    aint[c][nod*2].second+=aint[c][nod].second;
    aint[c][nod*2+1].second+=aint[c][nod].second;
    aint[c][nod*2].first+=aint[c][nod].second;
    aint[c][nod*2+1].first+=aint[c][nod].second;
    aint[c][nod].second=0;
}
void upd(int nod, int st, int dr, int le, int ri, int newv, int c)
{
    if(le>ri)
        return;
    if(le==st && dr==ri)
    {
        aint[c][nod].first += newv;
        aint[c][nod].second += newv;
        return;
    }
    propagate(nod,c);
    int mij=(st+dr)/2;
    upd(nod*2,st,mij,le,min(mij,ri),newv,c);
    upd(nod*2+1,mij+1,dr,max(mij+1,le),ri,newv,c);
    aint[c][nod].first = min(aint[c][nod*2].first, aint[c][nod*2+1].first);
}
void upd_poz(int nod, int st, int dr, int poz, int newv, int c)
{
    if(st==dr)
    {
        aint[c][nod].first = newv;
        return;
    }
}

void solve_big(int i)
{
    assert(isbig[trains[i].from]);
    dp[i] = min(dp[i], prec[trains[i].from] + trains[i].cost);
}
void baga_big(int id)
{
    for(int x:big_nodes)
    {
        prec[x]=INF;
        for(int y:train_ends[x])
        {
            if(meals[id].first > trains[y].tout)
            {
                inplus[y] = min(INF, inplus[y] + meal_cost[x]);
                calced[y] = min(INF, calced[y] + meal_cost[x]);
            }
            prec[x] = min(prec[x], calced[y]);
        }
    }
}
void update_big(int i, int W)
{
    while(poz_meals+1 < W && meals[poz_meals+1].second < trains[i].tin)
    {
        poz_meals++;
        baga_big(poz_meals);
        upd_aib(meals[poz_meals].first,+1);
    }
}
map<int,int> mp,nrm;
void normalizeaza(int M, int W)
{
    for(int i=0;i<M;i++)
    {
        mp[trains[i].tin]++;
        mp[trains[i].tout]++;
    }
    for(int i=0;i<W;i++)
    {
        mp[meals[i].first]++;
        mp[meals[i].second]++;
    }
    for(auto it:mp)
        if(it.second)
            nrm[it.first]=++cate;
    assert(cate<=400000);
    for(int i=0;i<M;i++)
    {
        trains[i].tin = nrm[trains[i].tin];
        trains[i].tout = nrm[trains[i].tout];
    }
    for(int i=0;i<W;i++)
    {
        meals[i].first = nrm[meals[i].first];
        meals[i].second = nrm[meals[i].second];
    }
}
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)
{
    meal_cost = T;
    for(int i=0;i<M;i++)
    {
        trains.push_back({X[i],Y[i],A[i],B[i],C[i]});
        cntin[trains[i].to]++;
        cntout[trains[i].from]++;
        calced[i]=INF;
        ids_tout.push_back(i);
    }
    for(int i=0;i<W;i++)
    {
        meals.push_back({L[i],R[i]});
    }
    sort(trains.begin(),trains.end(),cmp_trains);
    sort(meals.begin(),meals.end(),cmp_meals);
    sort(ids_tout.begin(),ids_tout.end(),cmp_tout);
    for(int i=0;i<M;i++)
        train_ends[trains[i].to].push_back(i);
    normalizeaza(M,W);
    for(int i=0;i<N;i++)
    {
        if(cntin[i]+cntout[i] > LIM)
        {
            isbig[i]=1;
            big_nodes.push_back(i);
            prec[i]=INF;
        }
    }
    int poz_tout=-1;
    for(int i=0;i<M;i++)
    {
        while(poz_tout+1 < (int)ids_tout.size() && trains[ids_tout[poz_tout+1]].tout <= trains[i].tin)
        {
            poz_tout++;
            int aux = ids_tout[poz_tout];

            calced[aux] = dp[aux];
            if(isbig[trains[aux].to]) prec[trains[aux].to] = min(prec[trains[aux].to], calced[aux]);
        }
        update_big(i,W);
        dp[i]=INF;
        if(trains[i].from==0)
        {
            dp[i] = min(dp[i], (long long)(poz_meals+1)*meal_cost[trains[i].from] + trains[i].cost);
        }
        if(isbig[trains[i].from])
            solve_big(i);
        else
            solve_small(i);
    }
    while(poz_meals+1 < W)
    {
        poz_meals++;
        upd_aib(meals[poz_meals].first,+1);
    }
    long long rez=INF;
    for(int i=0;i<M;i++)
    {
        if(trains[i].to==N-1)
        {
            rez = min(rez, dp[i] + (long long)qry_aib(trains[i].tout+1)*meal_cost[N-1]);
        }
    }
    if(rez==INF)
        return -1;
    else
        return rez;
}
/**

dp[i] = costul minim de a parcurge o ruta care incepe la nodul 0, a.i. ultimul tren luat sa fie i (cumparam un meal doar daca e obligatoriu)

*/

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