oj.uz

Submission #1104252

# Submission time Handle Problem Language Result Execution time Memory
1104252 2024-10-23T10:06:39 Z _8_8_ Train (APIO24_train) C++17
10 / 100
 314 ms 84376 KB 
#include "train.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int N = 1e5 + 12;

struct bit{
    vector<ll> t;
    int n;
    void init(int s) {
        n = s;
        t.assign(n + 1, 0);
    }
    void upd(int pos, ll val) {
        while(pos <= n) {
            t[pos] += val;
            pos += pos & -pos;    
        }
    }
    ll get(int i) {
        ll res = 0;
        while(i) {
            res += t[i];
            i -= i & -i;
        }
        return res;
    }
    ll get(int l, int r) {
        return get(r) - get(l - 1);
    }
}T;
int n, m, w, it = 0, ti = 0;
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;
int find(int pos) {
    int it = lower_bound(vt.begin(), vt.end(), pos) - vt.begin() + 1;
    return it;
}
ll cost(int L, int R) {
    assert(L <= R);
    return ti - T.get(find(L));
}
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));
    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;
    }
    int l = d[v].back().l, r = mx + 1;
    while(r - l > 1) {
        int mid = (l + r) >> 1;
        if(get_val(d[v].back(), mid) <= get_val(nv, mid)) {
            l = mid;
        } else {
            r = mid;
        }
    }
    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];
            add(y[j], dp[j], b[j]);
            it++;
        }
        while(ti < w && f[ti].second < a[i]) {
            col++;
            T.upd(find(f[ti].first), 1);
            ti++;
        }
        dp[i] = gdp(x[i], a[i]) + c[i];
    }
    if(dp[m - 1] >= inf) dp[m - 1] = -1;
    return dp[m - 1];
}


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 = _T;x = X;y = Y; a = A; b = B; c = 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++) {
        vt.push_back(L[i]);
        vt.push_back(R[i]);
        f.emplace_back(L[i], R[i]);
    }
    for(int i = 0; i < m; i++) {
        vt.push_back(a[i]);
        vt.push_back(b[i]);
    }
    vt.push_back(0);
    sort(vt.begin(), vt.end());
    vt.resize(unique(vt.begin(), vt.end()) - vt.begin());
    T.init((int)vt.size());
    sort(f.begin(), f.end(), [&](pair<int, int> x, pair<int, int> y){
        return x.second < y.second;
    });
	return get();
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 68424 KB Correct.
2 Correct 47 ms 68424 KB Correct.
3 Correct 44 ms 68332 KB Correct.
4 Correct 40 ms 68424 KB Correct.
5 Correct 42 ms 68168 KB Correct.
6 Correct 40 ms 68376 KB Correct.
7 Correct 40 ms 68216 KB Correct.

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 247 ms 77988 KB Correct.
2 Correct 182 ms 79004 KB Correct.
3 Correct 41 ms 68176 KB Correct.
4 Correct 50 ms 69448 KB Correct.
5 Correct 46 ms 68168 KB Correct.
6 Correct 282 ms 77980 KB Correct.
7 Correct 49 ms 68384 KB Correct.
8 Correct 215 ms 78404 KB Correct.
9 Correct 208 ms 79016 KB Correct.

Subtask #3
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 247 ms 77988 KB Correct.
2 Correct 182 ms 79004 KB Correct.
3 Correct 41 ms 68176 KB Correct.
4 Correct 50 ms 69448 KB Correct.
5 Correct 46 ms 68168 KB Correct.
6 Correct 282 ms 77980 KB Correct.
7 Correct 49 ms 68384 KB Correct.
8 Correct 215 ms 78404 KB Correct.
9 Correct 208 ms 79016 KB Correct.
10 Correct 314 ms 83360 KB Correct.
11 Correct 235 ms 84376 KB Correct.
12 Correct 52 ms 69444 KB Correct.
13 Correct 45 ms 68444 KB Correct.
14 Incorrect 299 ms 83012 KB Wrong Answer.
15 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 68424 KB Correct.
2 Correct 47 ms 68424 KB Correct.
3 Correct 44 ms 68332 KB Correct.
4 Correct 40 ms 68424 KB Correct.
5 Correct 42 ms 68168 KB Correct.
6 Correct 40 ms 68376 KB Correct.
7 Correct 40 ms 68216 KB Correct.
8 Correct 247 ms 77988 KB Correct.
9 Correct 182 ms 79004 KB Correct.
10 Correct 41 ms 68176 KB Correct.
11 Correct 50 ms 69448 KB Correct.
12 Correct 46 ms 68168 KB Correct.
13 Correct 282 ms 77980 KB Correct.
14 Correct 49 ms 68384 KB Correct.
15 Correct 215 ms 78404 KB Correct.
16 Correct 208 ms 79016 KB Correct.
17 Correct 314 ms 83360 KB Correct.
18 Correct 235 ms 84376 KB Correct.
19 Correct 52 ms 69444 KB Correct.
20 Correct 45 ms 68444 KB Correct.
21 Incorrect 299 ms 83012 KB Wrong Answer.
22 Halted 0 ms 0 KB -