oj.uz

Submission #1104232

# Submission time Handle Problem Language Result Execution time Memory
1104232 2024-10-23T09:42:33 Z _8_8_ Train (APIO24_train) C++17
5 / 100
 1000 ms 82624 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;
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 = 0;
    for(int i = 0; i < w; i++) {
        if(f[i].first > L && f[i].second < R) {
            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++) {
        // cout << i << ' ' << d[v][i].d << '\n';   
        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);
    int it = 0, ti = 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();
}

Compilation message

train.cpp: In function 'll get()':
train.cpp:87:17: warning: unused variable 'ti' [-Wunused-variable]
   87 |     int it = 0, ti = 0;
      |                 ^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 68432 KB Correct.
2 Correct 41 ms 68424 KB Correct.
3 Correct 42 ms 68440 KB Correct.
4 Correct 42 ms 68428 KB Correct.
5 Correct 42 ms 68320 KB Correct.
6 Correct 45 ms 68176 KB Correct.
7 Correct 43 ms 68280 KB Correct.

Subtask #2
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 77980 KB Correct.
2 Correct 112 ms 79012 KB Correct.
3 Correct 46 ms 68168 KB Correct.
4 Correct 53 ms 69960 KB Correct.
5 Correct 47 ms 68176 KB Correct.
6 Correct 132 ms 82624 KB Correct.
7 Correct 54 ms 68168 KB Correct.
8 Execution timed out 1054 ms 82456 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #3
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 77980 KB Correct.
2 Correct 112 ms 79012 KB Correct.
3 Correct 46 ms 68168 KB Correct.
4 Correct 53 ms 69960 KB Correct.
5 Correct 47 ms 68176 KB Correct.
6 Correct 132 ms 82624 KB Correct.
7 Correct 54 ms 68168 KB Correct.
8 Execution timed out 1054 ms 82456 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 68432 KB Correct.
2 Correct 41 ms 68424 KB Correct.
3 Correct 42 ms 68440 KB Correct.
4 Correct 42 ms 68428 KB Correct.
5 Correct 42 ms 68320 KB Correct.
6 Correct 45 ms 68176 KB Correct.
7 Correct 43 ms 68280 KB Correct.
8 Correct 105 ms 77980 KB Correct.
9 Correct 112 ms 79012 KB Correct.
10 Correct 46 ms 68168 KB Correct.
11 Correct 53 ms 69960 KB Correct.
12 Correct 47 ms 68176 KB Correct.
13 Correct 132 ms 82624 KB Correct.
14 Correct 54 ms 68168 KB Correct.
15 Execution timed out 1054 ms 82456 KB Time limit exceeded
16 Halted 0 ms 0 KB -