oj.uz

Submission #997362

# Submission time Handle Problem Language Result Execution time Memory
997362 2024-06-12T07:45:51 Z saddd Train (APIO24_train) C++17
100 / 100
 894 ms 182560 KB 
#include<bits/stdc++.h>
#include<fstream>
using namespace std;
#define sz(a) (int)a.size()
#define ALL(v) v.begin(), v.end()
#define ALLR(v) v.rbegin(), v.rend()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
#define mpp make_pair
const ld PI = 3.14159265359, prec = 1e-9;;
//using u128 = __uint128_t;
//const int x[4] = {1, 0, -1, 0};
//const int y[4] = {0, -1, 0, 1};
const ll mod = 1000003, pr = 31;
const int mxn = 2e5 + 5, mxq = 1e5 + 5, sq = 500, mxv = 5e4 + 1;
//const int base = (1 <<18);
const ll inf = 1e17 + 5, neg = -69420, inf2 = 1e14;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
// have fun!
#include "train.h"

#include <vector>
struct CC{
    vt<int>comp;
    void init(bool sign ){
        sort(ALL(comp)); 
        if(sign){
            comp.resize(unique(ALL(comp)) - comp.begin());
        }
    }
    int findl(int x){
        return(lower_bound(ALL(comp), x) - comp.begin() + 1);
    }
    int findr(int x){
        return(upper_bound(ALL(comp), x) - comp.begin() + 1);
    }
    void add(int x){
        comp.pb(x);
    }
};
CC cmpl, cmpr;
int lson[20 * mxn + 1], rson[20 * mxn + 1], sm[20 * mxn + 1], root[mxn + 1], cnt = 0;
struct E{
    ll x, y, a, b, c;
    bool operator <(const E &other){
        return(a < other.a);
    }
};

int n, m, w;
vt<E>edge;
vt<pll>food;
vt<int>comp;
deque<pii>mn[mxn + 1];
bool cmp(int a, int b){
    return(edge[a].b < edge[b].b);
}
ll t[mxn + 1], dp[mxn + 1];
void build(int nd, int l, int r){
    if(l == r)return;   
    int mid = (l + r) >> 1;
    lson[nd] = ++cnt; rson[nd] = ++cnt;
    build(lson[nd], l, mid); build(rson[nd], mid + 1, r);
}
void upd(int nd, int pre, int l, int r, int id){
    if(l == r){
        sm[nd] = sm[pre] + 1;
        return;
    }
    int mid = (l + r) >> 1;
    if(id <= mid){
        lson[nd] = ++cnt; rson[nd] = rson[pre];
        upd(lson[nd], lson[pre], l, mid, id);
    }else{
        lson[nd] = lson[pre];
        rson[nd] = ++cnt; upd(rson[nd], rson[pre], mid + 1, r, id);
    }
    sm[nd] = sm[lson[nd]] + sm[rson[nd]];
}
int get(int nd, int pre, int l, int r, int ql, int qr){
    if(ql > r || qr < l)return(0);
    if(ql <= l && qr >= r)return(sm[nd] - sm[pre]);
    int mid = (l + r) >> 1;
    return(max(0, get(lson[nd], lson[pre], l, mid, ql, qr) + get(rson[nd], rson[pre], mid + 1, r, ql, qr)));
}
ll getval(int ide, int rp){
   
    int lx = cmpl.findr(edge[ide].b) - 1, rx = cmpl.findr(cmpr.comp[rp - 1]) - 1;
    int ly = cmpr.findr(edge[ide].b), ry = rp;
    //cout << lx << " " << rx << " " << ly << " " << ry << "\n";
    if(lx > rx || ly > ry)return(dp[ide]); 
    ll ans = dp[ide] + get(root[rx], root[lx], 1, sz(cmpr.comp), ly, ry) * t[edge[ide].y];
    //cout << ans << " ";
    return(ans);
}
ll solve(){
    sort(ALL(edge));  sort(ALL(comp), cmp); sort(ALL(food));
    cmpr.add(0);
    for(int i = 0; i < sz(food); i++){
        cmpl.add(food[i].fi); cmpr.add(food[i].se);
    }
    cmpl.init(0); cmpr.init(1);
    root[0] = ++cnt;
    build(root[0], 1, sz(cmpr.comp));
    int rp = 0;
    for(int i = 1; i <= sz(food); i++){
        root[i] = ++cnt;
        upd(root[i], root[i - 1], 1, sz(cmpr.comp), cmpr.findl(food[i - 1].se));
    }
    rp = 0;
    ll ans = inf;
    mn[0].pb(mpp(m, 1));
    
    for(int i = 0; i < m; i++){
        while(rp < sz(comp) && edge[comp[rp]].b <= edge[i].a){
            if(dp[comp[rp]] == inf){
                rp++; continue;
            }
            auto [x, y, a, b, c] = edge[comp[rp]];
            
            while(sz(mn[y])){
                auto [ide, idr] = mn[y].back();
                if(getval(ide, idr) >= getval(comp[rp], idr)){
                    mn[y].pop_back();
                }else{
                    break;
                }
            }
            if(!sz(mn[y])){
                mn[y].pb(mpp(comp[rp], 1));
            }else{
                auto [ide, idr] = mn[y].back();
                int l = idr + 1, r = sz(cmpr.comp), ans = -1;
                while(l <= r){
                    int mid = (l + r) >> 1;
                    if(getval(comp[rp], mid) <= getval(ide, mid)){
                        ans = mid; r = mid - 1;
                    }else{
                        l = mid + 1;
                    }
                }
                if(ans != -1)mn[y].pb(mpp(comp[rp], ans));
            }
            rp++;
        }
        auto [x, y, a, b, c] = edge[i];
        int id = lower_bound(ALL(food), mpp(a, 1LL * -1)) - food.begin() - 1;
        if(sz(mn[x]) == 0)dp[i] = inf;
        else{
            int idr = cmpr.findl(a) - 1;
            while(sz(mn[x]) >= 2 && mn[x][1].se <= idr)mn[x].pop_front();
            
            dp[i] = getval(mn[x].front().fi, idr) + c;
            //cout << c << " ";
        }
        if(y == n - 1){
            int idl = cmpl.findr(edge[i].b) - 1, idr = cmpr.findr(edge[i].b);
            ll cnt = get(root[sz(cmpl.comp)], root[idl], 1, sz(cmpr.comp), idr, sz(cmpr.comp));
            ans = min(ans, dp[i] + cnt * t[n - 1]);
        }
        //cout << x << " " << y << " " << a << " " << b << " " << c << " " << dp[i] << "\n";
    }
    
    if(ans == inf)ans = -1;
    return(ans);
}
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) {
    edge.clear(); food.clear(); comp.clear();
    n = N; m = M; w = W;
    for(int i = 0; i < n; i++)t[i] = T[i];
    for(int i = 0; i < m; i++){
        edge.pb({X[i], Y[i], A[i], B[i], C[i]}); comp.pb(i);
    }
    for(int i = 0; i < w; i++){
        food.pb(mpp(L[i], R[i]));
    }
	return(solve());
}

Compilation message

train.cpp: In function 'long long int solve()':
train.cpp:156:13: warning: unused variable 'id' [-Wunused-variable]
  156 |         int id = lower_bound(ALL(food), mpp(a, 1LL * -1)) - food.begin() - 1;
      |             ^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 143960 KB Correct.
2 Correct 57 ms 143952 KB Correct.
3 Correct 56 ms 143956 KB Correct.
4 Correct 57 ms 143956 KB Correct.
5 Correct 56 ms 139924 KB Correct.
6 Correct 58 ms 143956 KB Correct.
7 Correct 57 ms 143952 KB Correct.

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 150228 KB Correct.
2 Correct 133 ms 151504 KB Correct.
3 Correct 56 ms 139856 KB Correct.
4 Correct 61 ms 140624 KB Correct.
5 Correct 54 ms 139856 KB Correct.
6 Correct 106 ms 150996 KB Correct.
7 Correct 50 ms 139748 KB Correct.
8 Correct 122 ms 150484 KB Correct.
9 Correct 150 ms 151124 KB Correct.

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 150228 KB Correct.
2 Correct 133 ms 151504 KB Correct.
3 Correct 56 ms 139856 KB Correct.
4 Correct 61 ms 140624 KB Correct.
5 Correct 54 ms 139856 KB Correct.
6 Correct 106 ms 150996 KB Correct.
7 Correct 50 ms 139748 KB Correct.
8 Correct 122 ms 150484 KB Correct.
9 Correct 150 ms 151124 KB Correct.
10 Correct 594 ms 180176 KB Correct.
11 Correct 377 ms 181960 KB Correct.
12 Correct 59 ms 140628 KB Correct.
13 Correct 56 ms 139856 KB Correct.
14 Correct 706 ms 180376 KB Correct.
15 Correct 399 ms 181596 KB Correct.
16 Correct 705 ms 180172 KB Correct.
17 Correct 810 ms 181192 KB Correct.

Subtask #4
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 143960 KB Correct.
2 Correct 57 ms 143952 KB Correct.
3 Correct 56 ms 143956 KB Correct.
4 Correct 57 ms 143956 KB Correct.
5 Correct 56 ms 139924 KB Correct.
6 Correct 58 ms 143956 KB Correct.
7 Correct 57 ms 143952 KB Correct.
8 Correct 122 ms 150228 KB Correct.
9 Correct 133 ms 151504 KB Correct.
10 Correct 56 ms 139856 KB Correct.
11 Correct 61 ms 140624 KB Correct.
12 Correct 54 ms 139856 KB Correct.
13 Correct 106 ms 150996 KB Correct.
14 Correct 50 ms 139748 KB Correct.
15 Correct 122 ms 150484 KB Correct.
16 Correct 150 ms 151124 KB Correct.
17 Correct 594 ms 180176 KB Correct.
18 Correct 377 ms 181960 KB Correct.
19 Correct 59 ms 140628 KB Correct.
20 Correct 56 ms 139856 KB Correct.
21 Correct 706 ms 180376 KB Correct.
22 Correct 399 ms 181596 KB Correct.
23 Correct 705 ms 180172 KB Correct.
24 Correct 810 ms 181192 KB Correct.
25 Correct 395 ms 181416 KB Correct.
26 Correct 409 ms 181852 KB Correct.
27 Correct 419 ms 181704 KB Correct.
28 Correct 465 ms 182560 KB Correct.
29 Correct 573 ms 180872 KB Correct.
30 Correct 594 ms 181196 KB Correct.
31 Correct 622 ms 180692 KB Correct.
32 Correct 639 ms 180220 KB Correct.
33 Correct 703 ms 180088 KB Correct.
34 Correct 743 ms 180680 KB Correct.
35 Correct 894 ms 180680 KB Correct.
36 Correct 556 ms 180176 KB Correct.
37 Correct 389 ms 180916 KB Correct.
38 Correct 691 ms 180936 KB Correct.
39 Correct 719 ms 180168 KB Correct.
40 Correct 406 ms 180936 KB Correct.
41 Correct 171 ms 177612 KB Correct.
42 Correct 155 ms 176132 KB Correct.
43 Correct 515 ms 176588 KB Correct.
44 Correct 403 ms 180812 KB Correct.
45 Correct 431 ms 181000 KB Correct.
46 Correct 389 ms 181448 KB Correct.
47 Correct 166 ms 160464 KB Correct.
48 Correct 151 ms 160644 KB Correct.
49 Correct 145 ms 160464 KB Correct.
50 Correct 154 ms 161088 KB Correct.
51 Correct 155 ms 160464 KB Correct.
52 Correct 154 ms 160864 KB Correct.