oj.uz

답안 #996748

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
996748 2024-06-11T06:47:13 Z ainta 은하철도 (APIO24_train) C++17
10 / 100
 504 ms 80068 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 && 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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 6748 KB Correct.
2 Correct 3 ms 6748 KB Correct.
3 Correct 2 ms 6748 KB Correct.
4 Correct 2 ms 6748 KB Correct.
5 Correct 2 ms 6748 KB Correct.
6 Correct 1 ms 6748 KB Correct.
7 Correct 1 ms 6748 KB Correct.

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 203 ms 27896 KB Correct.
2 Correct 142 ms 31428 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 335 ms 27080 KB Correct.
7 Correct 2 ms 6748 KB Correct.
8 Correct 287 ms 27676 KB Correct.
9 Correct 183 ms 31748 KB Correct.

Subtask #3
0.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 203 ms 27896 KB Correct.
2 Correct 142 ms 31428 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 335 ms 27080 KB Correct.
7 Correct 2 ms 6748 KB Correct.
8 Correct 287 ms 27676 KB Correct.
9 Correct 183 ms 31748 KB Correct.
10 Correct 493 ms 76996 KB Correct.
11 Correct 347 ms 80068 KB Correct.
12 Correct 8 ms 7516 KB Correct.
13 Correct 1 ms 6744 KB Correct.
14 Incorrect 504 ms 75464 KB Wrong Answer.
15 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 6748 KB Correct.
2 Correct 3 ms 6748 KB Correct.
3 Correct 2 ms 6748 KB Correct.
4 Correct 2 ms 6748 KB Correct.
5 Correct 2 ms 6748 KB Correct.
6 Correct 1 ms 6748 KB Correct.
7 Correct 1 ms 6748 KB Correct.
8 Correct 203 ms 27896 KB Correct.
9 Correct 142 ms 31428 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 335 ms 27080 KB Correct.
14 Correct 2 ms 6748 KB Correct.
15 Correct 287 ms 27676 KB Correct.
16 Correct 183 ms 31748 KB Correct.
17 Correct 493 ms 76996 KB Correct.
18 Correct 347 ms 80068 KB Correct.
19 Correct 8 ms 7516 KB Correct.
20 Correct 1 ms 6744 KB Correct.
21 Incorrect 504 ms 75464 KB Wrong Answer.
22 Halted 0 ms 0 KB -