oj.uz

Submission #1104233

# Submission time Handle Problem Language Result Execution time Memory
1104233 2024-10-23T09:44:04 Z _8_8_ Train (APIO24_train) C++17
5 / 100
 1000 ms 81820 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);
    int ret = ti;
    for(int i = 0; i < ti; i++) {
        if(f[i].first <= L) {
            ret--;
        }
    }
    return ret;
    // return col - 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]);
    }
    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 68452 KB Correct.
2 Correct 45 ms 68436 KB Correct.
3 Correct 50 ms 68336 KB Correct.
4 Correct 46 ms 68428 KB Correct.
5 Correct 48 ms 68168 KB Correct.
6 Correct 47 ms 68176 KB Correct.
7 Correct 51 ms 68168 KB Correct.

Subtask #2
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 80216 KB Correct.
2 Correct 128 ms 81820 KB Correct.
3 Correct 47 ms 68168 KB Correct.
4 Correct 54 ms 69960 KB Correct.
5 Correct 45 ms 68176 KB Correct.
6 Correct 133 ms 79004 KB Correct.
7 Correct 39 ms 68260 KB Correct.
8 Execution timed out 1076 ms 79012 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #3
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 80216 KB Correct.
2 Correct 128 ms 81820 KB Correct.
3 Correct 47 ms 68168 KB Correct.
4 Correct 54 ms 69960 KB Correct.
5 Correct 45 ms 68176 KB Correct.
6 Correct 133 ms 79004 KB Correct.
7 Correct 39 ms 68260 KB Correct.
8 Execution timed out 1076 ms 79012 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 68452 KB Correct.
2 Correct 45 ms 68436 KB Correct.
3 Correct 50 ms 68336 KB Correct.
4 Correct 46 ms 68428 KB Correct.
5 Correct 48 ms 68168 KB Correct.
6 Correct 47 ms 68176 KB Correct.
7 Correct 51 ms 68168 KB Correct.
8 Correct 127 ms 80216 KB Correct.
9 Correct 128 ms 81820 KB Correct.
10 Correct 47 ms 68168 KB Correct.
11 Correct 54 ms 69960 KB Correct.
12 Correct 45 ms 68176 KB Correct.
13 Correct 133 ms 79004 KB Correct.
14 Correct 39 ms 68260 KB Correct.
15 Execution timed out 1076 ms 79012 KB Time limit exceeded
16 Halted 0 ms 0 KB -