oj.uz

Submission #996739

# Submission time Handle Problem Language Result Execution time Memory
996739 2024-06-11T06:39:34 Z ainta Train (APIO24_train) C++17
10 / 100
 459 ms 80144 KB 
#include "train.h"
#include <bits/stdc++.h>
using namespace std;

#define rng(i,a,b) for(int i=int(a);i<=int(b);i++)
#define rep(i,b) rng(i,0,b-1)
#define gnr(i,b,a) for(int i=int(b);i>=int(a);i--)
#define per(i,b) gnr(i,b-1,0)
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed
#define si(x) int(x.size())
template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;
typedef long long ll;
using pii=pair<int,int>;
using vi=vc<int>;
using uint=unsigned;
using ull=unsigned long long;
using pil=pair<int,ll>;
using pli=pair<ll,int>;
using pll=pair<ll,ll>;
using t3=tuple<int,int,int>;

#define N_ 401000

struct Edge{
    int x, y, a, b, c;
};


struct Node{
    int l, r, s;
};
struct rangeCounter{
    vc<pii>LR;
    vc<Node>T;
    vi Root;
    int cnt, N;
    void Add(int nd, int p, int b, int e, int x){
        T[nd] = T[p];
        T[nd].s++;
        if(b==e)return;
        int m = (b+e)>>1;
        if(x<=m){
            T[nd].l = ++cnt;
            Add(T[nd].l, T[p].l, b,m,x);
        }
        else{
            T[nd].r = ++cnt;
            Add(T[nd].r, T[p].r, m+1,e,x);
        }
    }
    void init(int NN, vi &L, vi &R){
        LR.clear();
        cnt = 0;
        N = NN;
        int M = si(L);
        rep(i,M){
            LR.pb({L[i],R[i]});
        }
        sort(all(LR));
        Root.resize(M+1);
        T.resize((M+1)*30);
        Root[0] = 0;
        rep(i,M){
            Root[i+1] = ++cnt;
            Add(Root[i+1],Root[i], 0, N ,LR[i].se);
        }
    }
    int Sum(int nd, int b, int e, int r){
        if(b>r)return 0;
        if(e<=r)return T[nd].s;
        int m = (b+e)>>1;
        if(r<=m)return Sum(T[nd].l,b,m,r);
        else return T[T[nd].l].s + Sum(T[nd].r, m+1,e,r);
    }
    int Get(int l, int r){
        int pv = lower_bound(all(LR), pii(l,-1)) - LR.begin();
        return Sum(Root.back(), 0, N, r) - Sum(Root[pv], 0, N, r);
    }
}RC;

int TM;
ll INF = 1e18;

struct dp{
    vc<pil> Q;
    vi OV;
    int head;
    ll price;

    dp(){
        head=price=0;
    }

    ll getValue(pil p, int t){
        return p.se + price * RC.Get(p.fi+1, t);
    }

    int Over(pil p1, pil p2){ // p1.t < p2.t
        int b = p2.fi+1, e = TM-1, r=TM;
        while(b<=e){
            int mid = (b+e)>>1;
            if(getValue(p1,mid) >= getValue(p2,mid)){
                r=mid;
                e=mid-1;
            }
            else b=mid+1;
        }
        return r;
    }

    void Put(int t, ll cost){
        //Q.pb({t,cost});
        //return;
        while(head < si(Q) && Q.back().se >= cost){
            Q.pop_back();
            OV.pop_back();
        }
        if(head < si(Q) && Q.back().fi == t)return;
        
        int tp=0;
        while(head < si(Q)-1){
            int pv = si(Q)-1;
            if(tp <= OV[pv]){
                Q.pop_back();
                OV.pop_back();
            }
            else break;
            
        }
        Q.pb({t,cost});
        if(head < si(Q)-1){
            OV.pb(Over(Q[si(Q)-2],Q[si(Q)-1]));
        }
        else OV.pb(0);
    }

    ll Get(int t){
        while(head < si(Q)-1 && OV[head+1] <= t-1) head++;
        if(head >= si(Q))return INF;
        return getValue(Q[head],t-1);
/*        ll r=INF;
        rep(i,si(Q)){
            //printf("%d %lld\n",Q[i].fi,Q[i].se);
            r=min(r,getValue(Q[i],t-1));
        }
        return r;*/
    }
}D[101000];



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) {
    vi Z;
    rep(i,M){
        Z.pb(A[i]);
        Z.pb(B[i]);
    }
    rep(i,W){
        Z.pb(L[i]);
        Z.pb(R[i]);
    }
    sort(all(Z));


    auto ReNum = [&](vi &z, int t) -> int {
        return (lower_bound(all(z),t)-z.begin()) + 1;
    };
    rep(i,M){
        A[i]=ReNum(Z,A[i]);
        B[i]=ReNum(Z,B[i]);
    }
    rep(i,W){
        L[i]=ReNum(Z,L[i]);
        R[i]=ReNum(Z,R[i]);
    }


    TM = si(Z) + 1;

    RC.init(TM, L, R);

    vc<vc<Edge>> O(TM);
    vc<vc<pil>>UDT(TM);

    /*rep(i,W){
        printf("%d %d\n",L[i],R[i]);
    }
    puts("");*/

    rep(i,M){
        //printf("%d %d %d %d %d\n",X[i],Y[i],A[i],B[i],C[i]);
        O[A[i]].pb({X[i],Y[i],A[i],B[i],C[i]});
    }
    rep(i,N)D[i].price = T[i];

    D[0].Put(0,0);

    rep(i,TM){
        for(auto &[y,cost]: UDT[i]){
            D[y].Put(i,cost);
        }

        for(auto &[x,y,a,b,c]: O[i]){
            ll g = D[x].Get(a);
            if(g<INF){
                //printf("%d: %d %lld\n",y,b,g+c);
                UDT[b].pb({y,g+c});
            }
        }
    }
    ll t = D[N-1].Get(TM);
    if(t>8e17)return -1;
    return t;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6748 KB Correct.
2 Correct 2 ms 6824 KB Correct.
3 Correct 2 ms 6748 KB Correct.
4 Correct 2 ms 6748 KB Correct.
5 Correct 1 ms 6748 KB Correct.
6 Correct 1 ms 6748 KB Correct.
7 Correct 1 ms 6760 KB Correct.

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 27812 KB Correct.
2 Correct 125 ms 31508 KB Correct.
3 Correct 1 ms 6748 KB Correct.
4 Correct 7 ms 7516 KB Correct.
5 Correct 1 ms 6748 KB Correct.
6 Correct 251 ms 27052 KB Correct.
7 Correct 1 ms 6744 KB Correct.
8 Correct 252 ms 27740 KB Correct.
9 Correct 148 ms 31516 KB Correct.

Subtask #3
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 27812 KB Correct.
2 Correct 125 ms 31508 KB Correct.
3 Correct 1 ms 6748 KB Correct.
4 Correct 7 ms 7516 KB Correct.
5 Correct 1 ms 6748 KB Correct.
6 Correct 251 ms 27052 KB Correct.
7 Correct 1 ms 6744 KB Correct.
8 Correct 252 ms 27740 KB Correct.
9 Correct 148 ms 31516 KB Correct.
10 Correct 446 ms 76880 KB Correct.
11 Correct 287 ms 80144 KB Correct.
12 Correct 8 ms 7512 KB Correct.
13 Correct 1 ms 6748 KB Correct.
14 Incorrect 459 ms 75652 KB Wrong Answer.
15 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6748 KB Correct.
2 Correct 2 ms 6824 KB Correct.
3 Correct 2 ms 6748 KB Correct.
4 Correct 2 ms 6748 KB Correct.
5 Correct 1 ms 6748 KB Correct.
6 Correct 1 ms 6748 KB Correct.
7 Correct 1 ms 6760 KB Correct.
8 Correct 191 ms 27812 KB Correct.
9 Correct 125 ms 31508 KB Correct.
10 Correct 1 ms 6748 KB Correct.
11 Correct 7 ms 7516 KB Correct.
12 Correct 1 ms 6748 KB Correct.
13 Correct 251 ms 27052 KB Correct.
14 Correct 1 ms 6744 KB Correct.
15 Correct 252 ms 27740 KB Correct.
16 Correct 148 ms 31516 KB Correct.
17 Correct 446 ms 76880 KB Correct.
18 Correct 287 ms 80144 KB Correct.
19 Correct 8 ms 7512 KB Correct.
20 Correct 1 ms 6748 KB Correct.
21 Incorrect 459 ms 75652 KB Wrong Answer.
22 Halted 0 ms 0 KB -