oj.uz

Submission #996744

# Submission time Handle Problem Language Result Execution time Memory
996744 2024-06-11T06:44:49 Z ainta Train (APIO24_train) C++17
10 / 100
 474 ms 80064 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, 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;
        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 6748 KB Correct.
2 Correct 2 ms 6748 KB Correct.
3 Correct 2 ms 6748 KB Correct.
4 Correct 2 ms 6748 KB Correct.
5 Correct 2 ms 6744 KB Correct.
6 Correct 1 ms 6748 KB Correct.
7 Correct 1 ms 6748 KB Correct.

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 27844 KB Correct.
2 Correct 127 ms 31432 KB Correct.
3 Correct 1 ms 6748 KB Correct.
4 Correct 8 ms 7416 KB Correct.
5 Correct 1 ms 6748 KB Correct.
6 Correct 263 ms 27020 KB Correct.
7 Correct 1 ms 6744 KB Correct.
8 Correct 249 ms 27736 KB Correct.
9 Correct 159 ms 31512 KB Correct.

Subtask #3
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 27844 KB Correct.
2 Correct 127 ms 31432 KB Correct.
3 Correct 1 ms 6748 KB Correct.
4 Correct 8 ms 7416 KB Correct.
5 Correct 1 ms 6748 KB Correct.
6 Correct 263 ms 27020 KB Correct.
7 Correct 1 ms 6744 KB Correct.
8 Correct 249 ms 27736 KB Correct.
9 Correct 159 ms 31512 KB Correct.
10 Correct 418 ms 76988 KB Correct.
11 Correct 287 ms 80064 KB Correct.
12 Correct 12 ms 7512 KB Correct.
13 Correct 2 ms 6744 KB Correct.
14 Incorrect 474 ms 75524 KB Wrong Answer.
15 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6748 KB Correct.
2 Correct 2 ms 6748 KB Correct.
3 Correct 2 ms 6748 KB Correct.
4 Correct 2 ms 6748 KB Correct.
5 Correct 2 ms 6744 KB Correct.
6 Correct 1 ms 6748 KB Correct.
7 Correct 1 ms 6748 KB Correct.
8 Correct 194 ms 27844 KB Correct.
9 Correct 127 ms 31432 KB Correct.
10 Correct 1 ms 6748 KB Correct.
11 Correct 8 ms 7416 KB Correct.
12 Correct 1 ms 6748 KB Correct.
13 Correct 263 ms 27020 KB Correct.
14 Correct 1 ms 6744 KB Correct.
15 Correct 249 ms 27736 KB Correct.
16 Correct 159 ms 31512 KB Correct.
17 Correct 418 ms 76988 KB Correct.
18 Correct 287 ms 80064 KB Correct.
19 Correct 12 ms 7512 KB Correct.
20 Correct 2 ms 6744 KB Correct.
21 Incorrect 474 ms 75524 KB Wrong Answer.
22 Halted 0 ms 0 KB -