oj.uz

Submission #1104288

# Submission time Handle Problem Language Result Execution time Memory
1104288 2024-10-23T11:47:33 Z _8_8_ Train (APIO24_train) C++17
100 / 100
 731 ms 147956 KB 
#include "train.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int N = 1e5 + 12;

struct node{
    node *l = 0, *r = 0;
    int sum = 0;
    node(int val) {
        sum = val;
    }
    node(node *L, node *R) {
        l = L;
        r = R;
        sum = L->sum + R->sum;
    }
};
int s;
using pnode = node *;
pnode tt[N];
int n, m, w, it = 0, ti = 0;
vector<int> rs, ls;
pnode upd(int pos, pnode v, int tl = 0, int tr = s) {
    if(tl == tr) {
        return new node(v->sum + 1);
    } else {
        int tm = (tl + tr) >> 1;
        if(pos <= tm) {
            return new node(upd(pos, v->l, tl, tm), v->r); 
        } else {
            return new node(v->l, upd(pos, v->r, tm + 1, tr));
        }
    }
}
int get(int l, int r, pnode v, int tl = 0, int tr = s) {
    if(l > r || tl > r || l > tr) return 0;
    if(tl >= l && tr <= r) {
        return v->sum;
    } else {
        int tm = (tl + tr) >> 1;
        return get(l, r, v->l, tl, tm) + get(l, r, v->r, tm + 1, tr);
    }
}
vector<int> t, x, y, a, b, c, vt;
vector<pair<int, int>> f;
struct qwq{ 
    int pos;
    ll d;
    int l, r, v;
};
deque<qwq> d[N];
ll dp[N];

int col = 0;
const ll inf = 1e18, mx = (int)1e9 + 1;
ll cost(int L, int R) {
    int ret = 0, ret1 = 0;
    int it = lower_bound(rs.begin(), rs.end(), R) - rs.begin() - 1;
    int it1 = upper_bound(ls.begin(), ls.end(), L) - ls.begin() - 1;
    if(it < 0) {
        ret1 = 0;
    } else {
        ret1 = it + 1 - get(0, it1, tt[it]);
    }
    return ret1;
}
ll get_val(qwq q, int x) {
    if(x < q.pos) return inf;
    return q.d + cost(q.pos, x) * 1ll * t[q.v];
}
ll gdp(int v, int pos) {
    while(!d[v].empty() && d[v][0].r < pos) {
        d[v].pop_front();
    }
    if(d[v].empty()) return inf;
    ll ret = min(inf, get_val(d[v][0], pos));
    d[v][0].l = pos;
    return ret;
}

void add(int v, ll dd, int pos) {
    qwq nv;
    nv.pos = pos;nv.d = dd;nv.v = v;
    while(!d[v].empty() && get_val(d[v].back(), d[v].back().l) > get_val(nv, d[v].back().l)) {
        d[v].pop_back();
    }
    if(d[v].empty()) {
        d[v].push_back({pos, dd, pos, mx, v});
        return;
    }
    if(get_val(d[v].back(), mx) <= get_val(nv, mx)) {
        d[v].back().r = mx;
        return;
    }
    int l = 0, r = (int)vt.size() - 1;
    while(r - l > 1) {
        int mid = vt[(l + r) >> 1], mid1 = (l + r) >> 1;
        if(get_val(d[v].back(), mid) <= get_val(nv, mid)) {
            l = mid1;
        } else {
            r = mid1;
        }
    }
    r = vt[r];
    d[v].back().r = r - 1;
    if(r <= mx) {
        nv.l = r;
        nv.r = mx;
        d[v].push_back(nv);
    } 
}
ll get() {
    vector<int> e, ej;
    for(int i = 0; i < m; i++) {
        e.push_back(i);
        ej.push_back(i);
    }
    sort(e.begin(), e.end(), [&](int x, int y){
        return a[x] < a[y];
    });
    sort(ej.begin(), ej.end(), [&](int x, int y){
        return b[x] < b[y];
    });
    add(0, 0, 0);
    for(int i:e) {
        while(it < m && b[ej[it]] <= a[i]) {
            int j = ej[it];
            if(dp[j] < inf) add(y[j], dp[j], b[j]);
            it++;
        }
        dp[i] = gdp(x[i], a[i]) + c[i];
    }
    if(dp[m - 1] >= inf) dp[m - 1] = -1;
    return dp[m - 1];
}

pnode build(int tl = 0, int tr = s) {
    if(tl == tr) {
        return new node(0);
    } else {
        int tm = (tl + tr) >> 1;
        return new node(build(tl, tm), build(tm + 1, tr));
    }
}
ll solve(int N, int M, int W, vector<int> _T, vector<int> X, vector<int> Y, vector<int> A, vector<int> B, vector<int> C, vector<int> L,vector<int> R) {
    n = N;m = M;w = W;
    t.swap(_T);
    x.swap(X);
    y.swap(Y);
    a.swap(A);
    b.swap(B);
    c.swap(C);
    m++;
    x.push_back(n - 1);
    y.push_back(n - 1);
    a.push_back(mx);
    b.push_back(mx + 1);
    c.push_back(0);
    for(int i = 0; i < w; i++) {
        f.emplace_back(L[i], R[i]);
        rs.push_back(R[i]);
        ls.push_back(L[i]);
    }
    for(int i = 0; i < m; i++) {
        vt.push_back(a[i]);
        vt.push_back(b[i]);
    }
    vt.push_back(mx + 1);
    vt.push_back(0);
    sort(vt.begin(), vt.end());
    vt.resize(unique(vt.begin(), vt.end()) - vt.begin());
    sort(f.begin(), f.end(), [&](pair<int, int> x, pair<int, int> y){
        return x.second < y.second;
    });
    sort(rs.begin(), rs.end());
    sort(ls.begin(), ls.end());
    ls.resize(unique(ls.begin(), ls.end()) - ls.begin());
    s = (int)ls.size();
    pnode rt = build();
    for(int i = 0; i < w; i++) {
        int it = lower_bound(ls.begin(), ls.end(), f[i].first) - ls.begin();
        tt[i] = (i ? upd(it, tt[i - 1]) : upd(it, rt));
    }
	return get();
}

Compilation message

train.cpp: In function 'll cost(int, int)':
train.cpp:60:9: warning: unused variable 'ret' [-Wunused-variable]
   60 |     int ret = 0, ret1 = 0;
      |         ^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 68416 KB Correct.
2 Correct 40 ms 68340 KB Correct.
3 Correct 43 ms 68388 KB Correct.
4 Correct 40 ms 68380 KB Correct.
5 Correct 39 ms 68348 KB Correct.
6 Correct 41 ms 68176 KB Correct.
7 Correct 42 ms 68152 KB Correct.

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 74396 KB Correct.
2 Correct 137 ms 75160 KB Correct.
3 Correct 39 ms 68168 KB Correct.
4 Correct 48 ms 69040 KB Correct.
5 Correct 39 ms 68260 KB Correct.
6 Correct 103 ms 74404 KB Correct.
7 Correct 52 ms 68168 KB Correct.
8 Correct 95 ms 75164 KB Correct.
9 Correct 134 ms 75164 KB Correct.

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 74396 KB Correct.
2 Correct 137 ms 75160 KB Correct.
3 Correct 39 ms 68168 KB Correct.
4 Correct 48 ms 69040 KB Correct.
5 Correct 39 ms 68260 KB Correct.
6 Correct 103 ms 74404 KB Correct.
7 Correct 52 ms 68168 KB Correct.
8 Correct 95 ms 75164 KB Correct.
9 Correct 134 ms 75164 KB Correct.
10 Correct 587 ms 140124 KB Correct.
11 Correct 407 ms 140748 KB Correct.
12 Correct 48 ms 69148 KB Correct.
13 Correct 44 ms 68376 KB Correct.
14 Correct 408 ms 140080 KB Correct.
15 Correct 478 ms 140960 KB Correct.
16 Correct 472 ms 140164 KB Correct.
17 Correct 323 ms 141724 KB Correct.

Subtask #4
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 68416 KB Correct.
2 Correct 40 ms 68340 KB Correct.
3 Correct 43 ms 68388 KB Correct.
4 Correct 40 ms 68380 KB Correct.
5 Correct 39 ms 68348 KB Correct.
6 Correct 41 ms 68176 KB Correct.
7 Correct 42 ms 68152 KB Correct.
8 Correct 114 ms 74396 KB Correct.
9 Correct 137 ms 75160 KB Correct.
10 Correct 39 ms 68168 KB Correct.
11 Correct 48 ms 69040 KB Correct.
12 Correct 39 ms 68260 KB Correct.
13 Correct 103 ms 74404 KB Correct.
14 Correct 52 ms 68168 KB Correct.
15 Correct 95 ms 75164 KB Correct.
16 Correct 134 ms 75164 KB Correct.
17 Correct 587 ms 140124 KB Correct.
18 Correct 407 ms 140748 KB Correct.
19 Correct 48 ms 69148 KB Correct.
20 Correct 44 ms 68376 KB Correct.
21 Correct 408 ms 140080 KB Correct.
22 Correct 478 ms 140960 KB Correct.
23 Correct 472 ms 140164 KB Correct.
24 Correct 323 ms 141724 KB Correct.
25 Correct 524 ms 140956 KB Correct.
26 Correct 533 ms 140932 KB Correct.
27 Correct 550 ms 140972 KB Correct.
28 Correct 571 ms 140992 KB Correct.
29 Correct 731 ms 140176 KB Correct.
30 Correct 700 ms 145764 KB Correct.
31 Correct 618 ms 145688 KB Correct.
32 Correct 616 ms 145696 KB Correct.
33 Correct 524 ms 145380 KB Correct.
34 Correct 497 ms 145312 KB Correct.
35 Correct 510 ms 145420 KB Correct.
36 Correct 649 ms 145772 KB Correct.
37 Correct 511 ms 147904 KB Correct.
38 Correct 653 ms 145564 KB Correct.
39 Correct 540 ms 145392 KB Correct.
40 Correct 557 ms 147860 KB Correct.
41 Correct 237 ms 135580 KB Correct.
42 Correct 248 ms 134272 KB Correct.
43 Correct 552 ms 133788 KB Correct.
44 Correct 620 ms 147956 KB Correct.
45 Correct 537 ms 147868 KB Correct.
46 Correct 446 ms 147792 KB Correct.
47 Correct 352 ms 146588 KB Correct.
48 Correct 267 ms 140604 KB Correct.
49 Correct 317 ms 140700 KB Correct.
50 Correct 248 ms 138148 KB Correct.
51 Correct 231 ms 136604 KB Correct.
52 Correct 262 ms 138012 KB Correct.