oj.uz

Submission #1027271

# Submission time Handle Problem Language Result Execution time Memory
1027271 2024-07-19T03:01:55 Z bachhoangxuan Train (APIO24_train) C++17
100 / 100
 536 ms 157644 KB 
#include "train.h"
#include <bits/stdc++.h>
using namespace std;
using i32 = int;
#define int long long
const int inf = 1e18;
const int B = 1000;
const int D = 350;
const int maxn = 1e5+5;
const int maxs = 105;

struct Sum{
    vector<int> com;
    void add(int x){
        com.push_back(x);
    }
    void build(){
        sort(com.begin(),com.end());
        com.erase(unique(com.begin(),com.end()),com.end());
    }
    int cnt[maxn],total[maxn];
    void update(int x){
        //cout << "update " << x << '\n';
        x=lower_bound(com.begin(),com.end(),x)-com.begin()-1;
        if(x<0) return;
        for(int i=x/D-1;i>=0;i--) total[i]++;
        for(int i=x;i>=(x/D)*D;i--) cnt[i]++;
    }
    int get(int x){
        //cout << "get " << x << '\n';
        return cnt[x]+total[x/D];
    }
}V;

struct Block{
    int sz;
    vector<int> com;
    int tree[4*maxn],lazy[4*maxn];
    void add(int x){
        com.push_back(x);
    }
    void build(){
        sort(com.begin(),com.end());
        com.erase(unique(com.begin(),com.end()),com.end());
        sz=(int)com.size();
        for(int i=0;i<4*sz;i++) tree[i]=inf;
    }
    void update_pos(int l,int r,int id,int x,int val){
        if(l==r){
            tree[id]=min(tree[id],val);
            return;
        }
        int mid=(l+r)>>1;
        if(x<=mid) update_pos(l,mid,id<<1,x,val);
        else update_pos(mid+1,r,id<<1|1,x,val);
        tree[id]=min(tree[id<<1],tree[id<<1|1])+lazy[id];
    }
    void update_val(int l,int r,int id,int x,int val){
        if(x<l) return;
        if(r<=x){
            lazy[id]+=val;
            tree[id]+=val;
            return;
        }
        int mid=(l+r)>>1;
        update_val(l,mid,id<<1,x,val);
        update_val(mid+1,r,id<<1|1,x,val);
        tree[id]=min(tree[id<<1],tree[id<<1|1])+lazy[id];
    }
    int query(int l,int r,int id,int x){
        if(x<l) return inf;
        if(r<=x) return tree[id];
        int mid=(l+r)>>1;
        return min(query(l,mid,id<<1,x),query(mid+1,r,id<<1|1,x))+lazy[id];
    }

    void update_pos(int x,int val){
        x=lower_bound(com.begin(),com.end(),x)-com.begin();
        update_pos(0,sz-1,1,x,val);
    }
    void update_val(int x,int val){
        x=lower_bound(com.begin(),com.end(),x)-com.begin()-1;
        if(x<0) return;
        update_val(0,sz-1,1,x,val);
    }
    int query(int x){
        x=upper_bound(com.begin(),com.end(),x)-com.begin()-1;
        if(x<0) return inf;
        return query(0,sz-1,1,x);
    }
}S[maxs];
int f[maxn],pos[maxn],cnt;
vector<int> g[maxn];

int solve(i32 N, i32 M, i32 W, std::vector<i32> T, std::vector<i32> X, std::vector<i32> Y,
                std::vector<i32> P, std::vector<i32> Q, std::vector<i32> C, std::vector<i32> L,
                std::vector<i32> R) {

    for(int i=0;i<M;i++) f[Y[i]]++;
    for(int i=0;i<N;i++){
        if(f[i]>B) f[i]=++cnt,pos[cnt]=i;
        else f[i]=0;
    }
    for(int i=0;i<M;i++){
        if(f[Y[i]]) S[f[Y[i]]].add(Q[i]);
        V.add(Q[i]);
    }
    V.build();
    for(int i=1;i<=cnt;i++) S[i].build();

    vector<int> ord(M),meal(W),F(M);
    iota(ord.begin(),ord.end(),0);
    iota(meal.begin(),meal.end(),0);
    sort(ord.begin(),ord.end(),[&](int x,int y){return P[x]<P[y];});
    sort(meal.begin(),meal.end(),[&](int x,int y){return R[x]<R[y];});
    for(int i=0;i<M;i++) F[i]=lower_bound(V.com.begin(),V.com.end(),Q[i])-V.com.begin();

    int p=0;
    vector<int> dp(M,inf);
    int res=inf;
    auto add = [&](int id){
        //cout << "add " << id << '\n';
        V.update(L[id]);
        for(int i=1;i<=cnt;i++) S[i].update_val(L[id],T[pos[i]]);
    };
    for(int i:ord){
        while(p<W && R[meal[p]]<P[i]) add(meal[p++]);
        //cout << '*' << i << ' ' << p << '\n';
        if(!X[i]) dp[i]=1LL*p*T[X[i]];
        if(f[X[i]]) dp[i]=min(dp[i],S[f[X[i]]].query(P[i]));
        else{
            for(int j:g[X[i]]) if(Q[j]<=P[i]) dp[i]=min(dp[i],dp[j]+1LL*V.get(F[j])*T[X[i]]);
        }
        dp[i]+=C[i];
        if(f[Y[i]]) S[f[Y[i]]].update_pos(Q[i],dp[i]);
        else g[Y[i]].push_back(i);
    }

    sort(ord.begin(),ord.end(),[&](int x,int y){return Q[x]>Q[y];});
    sort(meal.begin(),meal.end(),[&](int x,int y){return L[x]>L[y];});
    p=0;
    for(int i:ord){
        while(p<W && L[meal[p]]>Q[i]) p++;
        if(Y[i]==N-1) res=min(res,dp[i]+1LL*p*T[N-1]);
    }
    return (res==inf?-1:res);
}
#undef int

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 134236 KB Correct.
2 Correct 12 ms 134376 KB Correct.
3 Correct 12 ms 134236 KB Correct.
4 Correct 12 ms 136332 KB Correct.
5 Correct 12 ms 134236 KB Correct.
6 Correct 13 ms 136320 KB Correct.
7 Correct 13 ms 134236 KB Correct.

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 142792 KB Correct.
2 Correct 82 ms 144072 KB Correct.
3 Correct 12 ms 134272 KB Correct.
4 Correct 17 ms 135504 KB Correct.
5 Correct 12 ms 134236 KB Correct.
6 Correct 111 ms 146380 KB Correct.
7 Correct 12 ms 136284 KB Correct.
8 Correct 64 ms 149700 KB Correct.
9 Correct 89 ms 148936 KB Correct.

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 142792 KB Correct.
2 Correct 82 ms 144072 KB Correct.
3 Correct 12 ms 134272 KB Correct.
4 Correct 17 ms 135504 KB Correct.
5 Correct 12 ms 134236 KB Correct.
6 Correct 111 ms 146380 KB Correct.
7 Correct 12 ms 136284 KB Correct.
8 Correct 64 ms 149700 KB Correct.
9 Correct 89 ms 148936 KB Correct.
10 Correct 124 ms 150904 KB Correct.
11 Correct 125 ms 153544 KB Correct.
12 Correct 19 ms 135516 KB Correct.
13 Correct 12 ms 136284 KB Correct.
14 Correct 179 ms 152908 KB Correct.
15 Correct 128 ms 155596 KB Correct.
16 Correct 536 ms 152776 KB Correct.
17 Correct 91 ms 154820 KB Correct.

Subtask #4
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 134236 KB Correct.
2 Correct 12 ms 134376 KB Correct.
3 Correct 12 ms 134236 KB Correct.
4 Correct 12 ms 136332 KB Correct.
5 Correct 12 ms 134236 KB Correct.
6 Correct 13 ms 136320 KB Correct.
7 Correct 13 ms 134236 KB Correct.
8 Correct 74 ms 142792 KB Correct.
9 Correct 82 ms 144072 KB Correct.
10 Correct 12 ms 134272 KB Correct.
11 Correct 17 ms 135504 KB Correct.
12 Correct 12 ms 134236 KB Correct.
13 Correct 111 ms 146380 KB Correct.
14 Correct 12 ms 136284 KB Correct.
15 Correct 64 ms 149700 KB Correct.
16 Correct 89 ms 148936 KB Correct.
17 Correct 124 ms 150904 KB Correct.
18 Correct 125 ms 153544 KB Correct.
19 Correct 19 ms 135516 KB Correct.
20 Correct 12 ms 136284 KB Correct.
21 Correct 179 ms 152908 KB Correct.
22 Correct 128 ms 155596 KB Correct.
23 Correct 536 ms 152776 KB Correct.
24 Correct 91 ms 154820 KB Correct.
25 Correct 138 ms 153544 KB Correct.
26 Correct 134 ms 153540 KB Correct.
27 Correct 146 ms 153544 KB Correct.
28 Correct 145 ms 157644 KB Correct.
29 Correct 121 ms 151148 KB Correct.
30 Correct 185 ms 152392 KB Correct.
31 Correct 160 ms 150428 KB Correct.
32 Correct 141 ms 150344 KB Correct.
33 Correct 246 ms 153028 KB Correct.
34 Correct 219 ms 152896 KB Correct.
35 Correct 235 ms 153032 KB Correct.
36 Correct 154 ms 152528 KB Correct.
37 Correct 127 ms 153544 KB Correct.
38 Correct 271 ms 152656 KB Correct.
39 Correct 154 ms 155080 KB Correct.
40 Correct 144 ms 155588 KB Correct.
41 Correct 131 ms 152572 KB Correct.
42 Correct 133 ms 151036 KB Correct.
43 Correct 159 ms 148416 KB Correct.
44 Correct 153 ms 155592 KB Correct.
45 Correct 139 ms 155592 KB Correct.
46 Correct 129 ms 153544 KB Correct.
47 Correct 95 ms 155328 KB Correct.
48 Correct 99 ms 157004 KB Correct.
49 Correct 108 ms 157128 KB Correct.
50 Correct 96 ms 154820 KB Correct.
51 Correct 91 ms 156676 KB Correct.
52 Correct 94 ms 156868 KB Correct.