oj.uz

Submission #1104246

# Submission time Handle Problem Language Result Execution time Memory
1104246 2024-10-23T10:02:13 Z _8_8_ Train (APIO24_train) C++17
10 / 100
 1000 ms 91288 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) {
    if(d[v].empty()) return inf;
    ll ret = inf;
    for(int i = 0; i < (int)d[v].size(); i++) {
        ret = min(ret, get_val(d[v][i], 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 = r;
        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 45 ms 68424 KB Correct.
2 Correct 53 ms 68424 KB Correct.
3 Correct 50 ms 68424 KB Correct.
4 Correct 50 ms 68424 KB Correct.
5 Correct 47 ms 68168 KB Correct.
6 Correct 48 ms 68176 KB Correct.
7 Correct 50 ms 68168 KB Correct.

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 361 ms 77980 KB Correct.
2 Correct 204 ms 79004 KB Correct.
3 Correct 47 ms 68168 KB Correct.
4 Correct 56 ms 69544 KB Correct.
5 Correct 45 ms 68168 KB Correct.
6 Correct 356 ms 77976 KB Correct.
7 Correct 50 ms 68168 KB Correct.
8 Correct 205 ms 78340 KB Correct.
9 Correct 192 ms 83880 KB Correct.

Subtask #3
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 361 ms 77980 KB Correct.
2 Correct 204 ms 79004 KB Correct.
3 Correct 47 ms 68168 KB Correct.
4 Correct 56 ms 69544 KB Correct.
5 Correct 45 ms 68168 KB Correct.
6 Correct 356 ms 77976 KB Correct.
7 Correct 50 ms 68168 KB Correct.
8 Correct 205 ms 78340 KB Correct.
9 Correct 192 ms 83880 KB Correct.
10 Correct 345 ms 89248 KB Correct.
11 Correct 221 ms 91288 KB Correct.
12 Correct 51 ms 69960 KB Correct.
13 Correct 42 ms 68372 KB Correct.
14 Execution timed out 1071 ms 88452 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 68424 KB Correct.
2 Correct 53 ms 68424 KB Correct.
3 Correct 50 ms 68424 KB Correct.
4 Correct 50 ms 68424 KB Correct.
5 Correct 47 ms 68168 KB Correct.
6 Correct 48 ms 68176 KB Correct.
7 Correct 50 ms 68168 KB Correct.
8 Correct 361 ms 77980 KB Correct.
9 Correct 204 ms 79004 KB Correct.
10 Correct 47 ms 68168 KB Correct.
11 Correct 56 ms 69544 KB Correct.
12 Correct 45 ms 68168 KB Correct.
13 Correct 356 ms 77976 KB Correct.
14 Correct 50 ms 68168 KB Correct.
15 Correct 205 ms 78340 KB Correct.
16 Correct 192 ms 83880 KB Correct.
17 Correct 345 ms 89248 KB Correct.
18 Correct 221 ms 91288 KB Correct.
19 Correct 51 ms 69960 KB Correct.
20 Correct 42 ms 68372 KB Correct.
21 Execution timed out 1071 ms 88452 KB Time limit exceeded
22 Halted 0 ms 0 KB -