oj.uz

Submission #1104243

# Submission time Handle Problem Language Result Execution time Memory
1104243 2024-10-23T09:51:15 Z _8_8_ Train (APIO24_train) C++17
5 / 100
 1000 ms 80544 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;
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) {
    d[v].push_back({pos, dd, 0, mx + 1, v});
    // if(d[v].empty()) {
    //     return;
    // }
}
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 51 ms 68424 KB Correct.
2 Correct 48 ms 68436 KB Correct.
3 Correct 45 ms 68468 KB Correct.
4 Correct 39 ms 68432 KB Correct.
5 Correct 44 ms 68372 KB Correct.
6 Correct 41 ms 68168 KB Correct.
7 Correct 56 ms 68168 KB Correct.

Subtask #2
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 78536 KB Correct.
2 Correct 145 ms 79200 KB Correct.
3 Correct 45 ms 68232 KB Correct.
4 Correct 56 ms 69328 KB Correct.
5 Correct 42 ms 68168 KB Correct.
6 Correct 883 ms 80544 KB Correct.
7 Correct 44 ms 68208 KB Correct.
8 Execution timed out 1077 ms 79624 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #3
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 78536 KB Correct.
2 Correct 145 ms 79200 KB Correct.
3 Correct 45 ms 68232 KB Correct.
4 Correct 56 ms 69328 KB Correct.
5 Correct 42 ms 68168 KB Correct.
6 Correct 883 ms 80544 KB Correct.
7 Correct 44 ms 68208 KB Correct.
8 Execution timed out 1077 ms 79624 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 68424 KB Correct.
2 Correct 48 ms 68436 KB Correct.
3 Correct 45 ms 68468 KB Correct.
4 Correct 39 ms 68432 KB Correct.
5 Correct 44 ms 68372 KB Correct.
6 Correct 41 ms 68168 KB Correct.
7 Correct 56 ms 68168 KB Correct.
8 Correct 205 ms 78536 KB Correct.
9 Correct 145 ms 79200 KB Correct.
10 Correct 45 ms 68232 KB Correct.
11 Correct 56 ms 69328 KB Correct.
12 Correct 42 ms 68168 KB Correct.
13 Correct 883 ms 80544 KB Correct.
14 Correct 44 ms 68208 KB Correct.
15 Execution timed out 1077 ms 79624 KB Time limit exceeded
16 Halted 0 ms 0 KB -