oj.uz

Submission #1104244

# Submission time Handle Problem Language Result Execution time Memory
1104244 2024-10-23T09:54:04 Z _8_8_ Train (APIO24_train) C++17
5 / 100
 1000 ms 80524 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) {
    d[v].push_back({pos, dd, pos, mx, v});
    // 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;
    // }

}
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 48 ms 68432 KB Correct.
2 Correct 47 ms 68444 KB Correct.
3 Correct 48 ms 68424 KB Correct.
4 Correct 45 ms 68336 KB Correct.
5 Correct 47 ms 68168 KB Correct.
6 Correct 41 ms 68296 KB Correct.
7 Correct 41 ms 68172 KB Correct.

Subtask #2
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 78492 KB Correct.
2 Correct 132 ms 79004 KB Correct.
3 Correct 41 ms 68168 KB Correct.
4 Correct 48 ms 69388 KB Correct.
5 Correct 46 ms 68320 KB Correct.
6 Correct 804 ms 80524 KB Correct.
7 Correct 43 ms 68168 KB Correct.
8 Execution timed out 1072 ms 79516 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #3
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 78492 KB Correct.
2 Correct 132 ms 79004 KB Correct.
3 Correct 41 ms 68168 KB Correct.
4 Correct 48 ms 69388 KB Correct.
5 Correct 46 ms 68320 KB Correct.
6 Correct 804 ms 80524 KB Correct.
7 Correct 43 ms 68168 KB Correct.
8 Execution timed out 1072 ms 79516 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 68432 KB Correct.
2 Correct 47 ms 68444 KB Correct.
3 Correct 48 ms 68424 KB Correct.
4 Correct 45 ms 68336 KB Correct.
5 Correct 47 ms 68168 KB Correct.
6 Correct 41 ms 68296 KB Correct.
7 Correct 41 ms 68172 KB Correct.
8 Correct 194 ms 78492 KB Correct.
9 Correct 132 ms 79004 KB Correct.
10 Correct 41 ms 68168 KB Correct.
11 Correct 48 ms 69388 KB Correct.
12 Correct 46 ms 68320 KB Correct.
13 Correct 804 ms 80524 KB Correct.
14 Correct 43 ms 68168 KB Correct.
15 Execution timed out 1072 ms 79516 KB Time limit exceeded
16 Halted 0 ms 0 KB -