oj.uz

Submission #996749

# Submission time Handle Problem Language Result Execution time Memory
996749 2024-06-11T06:48:55 Z ainta Train (APIO24_train) C++17
100 / 100
 859 ms 76228 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;
    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, 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){
        while(head < si(Q) && Q.back().se >= cost){
            Q.pop_back();
        }
        if(head < si(Q) && Q.back().fi == t)return;
        
        while(head < si(Q)-1){
            int pv = si(Q)-1;
            if(Over(Q[pv-1],Q[pv]) >= Over(Q[pv],pil(t,cost))){
                Q.pop_back();
            }
            else break;
            
        }
        Q.pb({t,cost});
    }

    ll Get(int t){
        while(head < si(Q)-1 && getValue(Q[head],t-1) >= getValue(Q[head+1],t-1)) head++;
        if(head >= si(Q))return INF;
        return getValue(Q[head],t-1);
        /*ll r=INF;
        printf("%d\n",t);
        rep(i,si(Q)){
            printf("%d %lld: %d\n",Q[i].fi,Q[i].se, OV[i]);
            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 2 ms 4444 KB Correct.
2 Correct 2 ms 4444 KB Correct.
3 Correct 2 ms 4440 KB Correct.
4 Correct 2 ms 4444 KB Correct.
5 Correct 1 ms 4184 KB Correct.
6 Correct 1 ms 4188 KB Correct.
7 Correct 1 ms 4188 KB Correct.

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 25196 KB Correct.
2 Correct 102 ms 27328 KB Correct.
3 Correct 1 ms 4184 KB Correct.
4 Correct 9 ms 4952 KB Correct.
5 Correct 1 ms 4188 KB Correct.
6 Correct 295 ms 24768 KB Correct.
7 Correct 2 ms 4184 KB Correct.
8 Correct 459 ms 25512 KB Correct.
9 Correct 130 ms 27412 KB Correct.

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 25196 KB Correct.
2 Correct 102 ms 27328 KB Correct.
3 Correct 1 ms 4184 KB Correct.
4 Correct 9 ms 4952 KB Correct.
5 Correct 1 ms 4188 KB Correct.
6 Correct 295 ms 24768 KB Correct.
7 Correct 2 ms 4184 KB Correct.
8 Correct 459 ms 25512 KB Correct.
9 Correct 130 ms 27412 KB Correct.
10 Correct 229 ms 74176 KB Correct.
11 Correct 183 ms 75716 KB Correct.
12 Correct 9 ms 4952 KB Correct.
13 Correct 1 ms 4188 KB Correct.
14 Correct 395 ms 73304 KB Correct.
15 Correct 223 ms 75844 KB Correct.
16 Correct 349 ms 73552 KB Correct.
17 Correct 859 ms 74180 KB Correct.

Subtask #4
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4444 KB Correct.
2 Correct 2 ms 4444 KB Correct.
3 Correct 2 ms 4440 KB Correct.
4 Correct 2 ms 4444 KB Correct.
5 Correct 1 ms 4184 KB Correct.
6 Correct 1 ms 4188 KB Correct.
7 Correct 1 ms 4188 KB Correct.
8 Correct 171 ms 25196 KB Correct.
9 Correct 102 ms 27328 KB Correct.
10 Correct 1 ms 4184 KB Correct.
11 Correct 9 ms 4952 KB Correct.
12 Correct 1 ms 4188 KB Correct.
13 Correct 295 ms 24768 KB Correct.
14 Correct 2 ms 4184 KB Correct.
15 Correct 459 ms 25512 KB Correct.
16 Correct 130 ms 27412 KB Correct.
17 Correct 229 ms 74176 KB Correct.
18 Correct 183 ms 75716 KB Correct.
19 Correct 9 ms 4952 KB Correct.
20 Correct 1 ms 4188 KB Correct.
21 Correct 395 ms 73304 KB Correct.
22 Correct 223 ms 75844 KB Correct.
23 Correct 349 ms 73552 KB Correct.
24 Correct 859 ms 74180 KB Correct.
25 Correct 229 ms 75820 KB Correct.
26 Correct 220 ms 75976 KB Correct.
27 Correct 250 ms 75968 KB Correct.
28 Correct 271 ms 76228 KB Correct.
29 Correct 232 ms 74432 KB Correct.
30 Correct 255 ms 73732 KB Correct.
31 Correct 260 ms 73664 KB Correct.
32 Correct 226 ms 73928 KB Correct.
33 Correct 430 ms 73268 KB Correct.
34 Correct 405 ms 73284 KB Correct.
35 Correct 545 ms 73552 KB Correct.
36 Correct 241 ms 73788 KB Correct.
37 Correct 213 ms 75968 KB Correct.
38 Correct 328 ms 73668 KB Correct.
39 Correct 471 ms 73048 KB Correct.
40 Correct 213 ms 75996 KB Correct.
41 Correct 160 ms 70348 KB Correct.
42 Correct 180 ms 69508 KB Correct.
43 Correct 392 ms 71364 KB Correct.
44 Correct 293 ms 75968 KB Correct.
45 Correct 228 ms 75968 KB Correct.
46 Correct 224 ms 75716 KB Correct.
47 Correct 790 ms 73540 KB Correct.
48 Correct 729 ms 73668 KB Correct.
49 Correct 782 ms 73664 KB Correct.
50 Correct 714 ms 73548 KB Correct.
51 Correct 701 ms 73668 KB Correct.
52 Correct 774 ms 73664 KB Correct.