oj.uz

Submission #1104251

# Submission time Handle Problem Language Result Execution time Memory
1104251 2024-10-23T10:06:03 Z _8_8_ Train (APIO24_train) C++17
5 / 100
 296 ms 88176 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);
    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 49 ms 68424 KB Correct.
2 Incorrect 45 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 275 ms 77992 KB Correct.
2 Correct 204 ms 79004 KB Correct.
3 Correct 42 ms 68168 KB Correct.
4 Correct 49 ms 69528 KB Correct.
5 Correct 45 ms 68168 KB Correct.
6 Correct 253 ms 77980 KB Correct.
7 Correct 43 ms 68168 KB Correct.
8 Correct 202 ms 78496 KB Correct.
9 Correct 195 ms 81820 KB Correct.

Subtask #3
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 275 ms 77992 KB Correct.
2 Correct 204 ms 79004 KB Correct.
3 Correct 42 ms 68168 KB Correct.
4 Correct 49 ms 69528 KB Correct.
5 Correct 45 ms 68168 KB Correct.
6 Correct 253 ms 77980 KB Correct.
7 Correct 43 ms 68168 KB Correct.
8 Correct 202 ms 78496 KB Correct.
9 Correct 195 ms 81820 KB Correct.
10 Correct 296 ms 83352 KB Correct.
11 Correct 218 ms 88176 KB Correct.
12 Correct 48 ms 69960 KB Correct.
13 Correct 42 ms 68168 KB Correct.
14 Incorrect 270 ms 85984 KB Wrong Answer.
15 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

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