oj.uz

Submission #1104239

# Submission time Handle Problem Language Result Execution time Memory
1104239 2024-10-23T09:47:52 Z _8_8_ Train (APIO24_train) C++17
5 / 100
 1000 ms 78188 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;
};
deque<qwq> d[N];
ll dp[N];

void add(int v, ll dd, int pos) {
    d[v].push_back({pos, dd});
}
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 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, d[v][i].d + cost(d[v][i].pos, pos) * 1ll * t[v]);
    }
    return ret;
}

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 49 ms 66888 KB Correct.
2 Correct 50 ms 66888 KB Correct.
3 Correct 50 ms 66892 KB Correct.
4 Correct 48 ms 66888 KB Correct.
5 Correct 50 ms 66640 KB Correct.
6 Correct 45 ms 66632 KB Correct.
7 Correct 44 ms 66632 KB Correct.

Subtask #2
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 76444 KB Correct.
2 Correct 142 ms 77472 KB Correct.
3 Correct 44 ms 66640 KB Correct.
4 Correct 70 ms 67980 KB Correct.
5 Correct 48 ms 66588 KB Correct.
6 Correct 890 ms 78188 KB Correct.
7 Correct 49 ms 66732 KB Correct.
8 Execution timed out 1076 ms 77688 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #3
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 76444 KB Correct.
2 Correct 142 ms 77472 KB Correct.
3 Correct 44 ms 66640 KB Correct.
4 Correct 70 ms 67980 KB Correct.
5 Correct 48 ms 66588 KB Correct.
6 Correct 890 ms 78188 KB Correct.
7 Correct 49 ms 66732 KB Correct.
8 Execution timed out 1076 ms 77688 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 66888 KB Correct.
2 Correct 50 ms 66888 KB Correct.
3 Correct 50 ms 66892 KB Correct.
4 Correct 48 ms 66888 KB Correct.
5 Correct 50 ms 66640 KB Correct.
6 Correct 45 ms 66632 KB Correct.
7 Correct 44 ms 66632 KB Correct.
8 Correct 204 ms 76444 KB Correct.
9 Correct 142 ms 77472 KB Correct.
10 Correct 44 ms 66640 KB Correct.
11 Correct 70 ms 67980 KB Correct.
12 Correct 48 ms 66588 KB Correct.
13 Correct 890 ms 78188 KB Correct.
14 Correct 49 ms 66732 KB Correct.
15 Execution timed out 1076 ms 77688 KB Time limit exceeded
16 Halted 0 ms 0 KB -