oj.uz

Submission #1104249

# Submission time Handle Problem Language Result Execution time Memory
1104249 2024-10-23T10:04:50 Z _8_8_ Train (APIO24_train) C++17
5 / 100
 310 ms 84504 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 = get_val(d[v][0], pos);
    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 = 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
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 68432 KB Correct.
2 Incorrect 46 ms 68424 KB Integer 1000000000000188553 violates the range [-1, 10^18]
3 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 268 ms 77980 KB Correct.
2 Correct 207 ms 79056 KB Correct.
3 Correct 45 ms 68168 KB Correct.
4 Correct 52 ms 69452 KB Correct.
5 Correct 50 ms 68168 KB Correct.
6 Correct 295 ms 78064 KB Correct.
7 Correct 49 ms 68164 KB Correct.
8 Correct 218 ms 78236 KB Correct.
9 Correct 218 ms 79204 KB Correct.

Subtask #3
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 268 ms 77980 KB Correct.
2 Correct 207 ms 79056 KB Correct.
3 Correct 45 ms 68168 KB Correct.
4 Correct 52 ms 69452 KB Correct.
5 Correct 50 ms 68168 KB Correct.
6 Correct 295 ms 78064 KB Correct.
7 Correct 49 ms 68164 KB Correct.
8 Correct 218 ms 78236 KB Correct.
9 Correct 218 ms 79204 KB Correct.
10 Correct 310 ms 83352 KB Correct.
11 Correct 235 ms 84504 KB Correct.
12 Correct 53 ms 69448 KB Correct.
13 Correct 47 ms 68276 KB Correct.
14 Incorrect 288 ms 83108 KB Wrong Answer.
15 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 68432 KB Correct.
2 Incorrect 46 ms 68424 KB Integer 1000000000000188553 violates the range [-1, 10^18]
3 Halted 0 ms 0 KB -