oj.uz

Submission #1104237

# Submission time Handle Problem Language Result Execution time Memory
1104237 2024-10-23T09:46:50 Z _8_8_ Train (APIO24_train) C++17
5 / 100
 1000 ms 79044 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;
};
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 48 ms 68248 KB Correct.
2 Correct 39 ms 68312 KB Correct.
3 Correct 41 ms 68324 KB Correct.
4 Correct 40 ms 68440 KB Correct.
5 Correct 42 ms 68168 KB Correct.
6 Correct 41 ms 68348 KB Correct.
7 Correct 42 ms 68176 KB Correct.

Subtask #2
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 77980 KB Correct.
2 Correct 142 ms 79004 KB Correct.
3 Correct 45 ms 68244 KB Correct.
4 Correct 52 ms 69448 KB Correct.
5 Correct 43 ms 68228 KB Correct.
6 Correct 887 ms 79044 KB Correct.
7 Correct 48 ms 68232 KB Correct.
8 Execution timed out 1068 ms 78760 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #3
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 77980 KB Correct.
2 Correct 142 ms 79004 KB Correct.
3 Correct 45 ms 68244 KB Correct.
4 Correct 52 ms 69448 KB Correct.
5 Correct 43 ms 68228 KB Correct.
6 Correct 887 ms 79044 KB Correct.
7 Correct 48 ms 68232 KB Correct.
8 Execution timed out 1068 ms 78760 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 68248 KB Correct.
2 Correct 39 ms 68312 KB Correct.
3 Correct 41 ms 68324 KB Correct.
4 Correct 40 ms 68440 KB Correct.
5 Correct 42 ms 68168 KB Correct.
6 Correct 41 ms 68348 KB Correct.
7 Correct 42 ms 68176 KB Correct.
8 Correct 198 ms 77980 KB Correct.
9 Correct 142 ms 79004 KB Correct.
10 Correct 45 ms 68244 KB Correct.
11 Correct 52 ms 69448 KB Correct.
12 Correct 43 ms 68228 KB Correct.
13 Correct 887 ms 79044 KB Correct.
14 Correct 48 ms 68232 KB Correct.
15 Execution timed out 1068 ms 78760 KB Time limit exceeded
16 Halted 0 ms 0 KB -