oj.uz

Submission #1104272

# Submission time Handle Problem Language Result Execution time Memory
1104272 2024-10-23T11:18:32 Z _8_8_ Train (APIO24_train) C++17
40 / 100
 1000 ms 146308 KB 
#include "train.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int N = 1e5 + 12;

struct node{
    node *l = 0, *r = 0;
    int sum = 0;
    node(int val) {
        sum = val;
    }
    node(node *L, node *R) {
        l = L;
        r = R;
        sum = L->sum + R->sum;
    }
};
int s;
using pnode = node *;
pnode tt[N];
int n, m, w, it = 0, ti = 0;
vector<int> rs, ls;
pnode upd(int pos, pnode v, int tl = 0, int tr = s) {
    if(tl == tr) {
        return new node(v->sum + 1);
    } else {
        int tm = (tl + tr) >> 1;
        if(pos <= tm) {
            return new node(upd(pos, v->l, tl, tm), v->r); 
        } else {
            return new node(v->l, upd(pos, v->r, tm + 1, tr));
        }
    }
}
int get(int l, int r, pnode v, int tl = 0, int tr = s) {
    if(l > r || tl > r || l > tr) return 0;
    if(tl >= l && tr <= r) {
        return v->sum;
    } else {
        int tm = (tl + tr) >> 1;
        return get(l, r, v->l, tl, tm) + get(l, r, v->r, tm + 1, tr);
    }
}
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;
ll cost(int L, int R) {
    int ret = 0, ret1 = 0;
    int it = lower_bound(rs.begin(), rs.end(), R) - rs.begin() - 1;
    int it1 = upper_bound(ls.begin(), ls.end(), L) - ls.begin() - 1;

    if(it < 0) {
        ret1 = 0;
    } else {
        ret1 = it + 1 - get(0, it1, tt[it]);
    }
    return ret1;
}
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) {
    while(!d[v].empty() && d[v][0].r < pos) {
        d[v].pop_front();
    }
    if(d[v].empty()) return inf;
    ll ret = min(inf, get_val(d[v][0], pos));
    d[v][0].l = pos;
    return ret;
}

void add(int v, ll dd, int pos) {
    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;
    }
    if(get_val(d[v].back(), mx) <= get_val(nv, mx)) {
        d[v].back().r = mx;
        return;
    }
    int l = d[v].back().l, r = mx + 1;
    while(r - l > 1) {
        int mid = (l + r) >> 1;
        if(get_val(d[v].back(), mid) <= get_val(nv, mid)) {
            l = mid;
        } else {
            r = mid;
        }
    }
    d[v].back().r = r - 1;
    if(r <= mx) {
        nv.l = r;
        nv.r = mx;
        d[v].push_back(nv);
    } 
}
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];
            if(dp[j] != inf)add(y[j], dp[j], b[j]);
            it++;
        }
        dp[i] = gdp(x[i], a[i]) + c[i];
    }
    if(dp[m - 1] >= inf) dp[m - 1] = -1;
    return dp[m - 1];
}

pnode build(int tl = 0, int tr = s) {
    if(tl == tr) {
        return new node(0);
    } else {
        int tm = (tl + tr) >> 1;
        return new node(build(tl, tm), build(tm + 1, tr));
    }
}
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++) {
        f.emplace_back(L[i], R[i]);
        rs.push_back(R[i]);
        ls.push_back(L[i]);
    }
    sort(f.begin(), f.end(), [&](pair<int, int> x, pair<int, int> y){
        return x.second < y.second;
    });
    sort(rs.begin(), rs.end());
    sort(ls.begin(), ls.end());
    ls.resize(unique(ls.begin(), ls.end()) - ls.begin());
    s = (int)ls.size();
    pnode rt = build();
    for(int i = 0; i < w; i++) {
        int it = lower_bound(ls.begin(), ls.end(), f[i].first) - ls.begin();
        tt[i] = (i ? upd(it, tt[i - 1]) : upd(it, rt));
    }
	return get();
}

Compilation message

train.cpp: In function 'll cost(int, int)':
train.cpp:60:9: warning: unused variable 'ret' [-Wunused-variable]
   60 |     int ret = 0, ret1 = 0;
      |         ^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 68424 KB Correct.
2 Correct 44 ms 68272 KB Correct.
3 Correct 41 ms 68424 KB Correct.
4 Correct 39 ms 68432 KB Correct.
5 Correct 38 ms 68164 KB Correct.
6 Correct 41 ms 68168 KB Correct.
7 Correct 45 ms 68288 KB Correct.

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 75680 KB Correct.
2 Correct 135 ms 76704 KB Correct.
3 Correct 48 ms 68220 KB Correct.
4 Correct 56 ms 69448 KB Correct.
5 Correct 62 ms 68284 KB Correct.
6 Correct 105 ms 75680 KB Correct.
7 Correct 44 ms 68176 KB Correct.
8 Correct 111 ms 76708 KB Correct.
9 Correct 133 ms 76796 KB Correct.

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 75680 KB Correct.
2 Correct 135 ms 76704 KB Correct.
3 Correct 48 ms 68220 KB Correct.
4 Correct 56 ms 69448 KB Correct.
5 Correct 62 ms 68284 KB Correct.
6 Correct 105 ms 75680 KB Correct.
7 Correct 44 ms 68176 KB Correct.
8 Correct 111 ms 76708 KB Correct.
9 Correct 133 ms 76796 KB Correct.
10 Correct 913 ms 144132 KB Correct.
11 Correct 580 ms 142748 KB Correct.
12 Correct 57 ms 69388 KB Correct.
13 Correct 50 ms 68264 KB Correct.
14 Correct 648 ms 141388 KB Correct.
15 Correct 552 ms 146308 KB Correct.
16 Correct 685 ms 141380 KB Correct.
17 Correct 469 ms 143260 KB Correct.

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 68424 KB Correct.
2 Correct 44 ms 68272 KB Correct.
3 Correct 41 ms 68424 KB Correct.
4 Correct 39 ms 68432 KB Correct.
5 Correct 38 ms 68164 KB Correct.
6 Correct 41 ms 68168 KB Correct.
7 Correct 45 ms 68288 KB Correct.
8 Correct 132 ms 75680 KB Correct.
9 Correct 135 ms 76704 KB Correct.
10 Correct 48 ms 68220 KB Correct.
11 Correct 56 ms 69448 KB Correct.
12 Correct 62 ms 68284 KB Correct.
13 Correct 105 ms 75680 KB Correct.
14 Correct 44 ms 68176 KB Correct.
15 Correct 111 ms 76708 KB Correct.
16 Correct 133 ms 76796 KB Correct.
17 Correct 913 ms 144132 KB Correct.
18 Correct 580 ms 142748 KB Correct.
19 Correct 57 ms 69388 KB Correct.
20 Correct 50 ms 68264 KB Correct.
21 Correct 648 ms 141388 KB Correct.
22 Correct 552 ms 146308 KB Correct.
23 Correct 685 ms 141380 KB Correct.
24 Correct 469 ms 143260 KB Correct.
25 Correct 637 ms 142544 KB Correct.
26 Correct 752 ms 142492 KB Correct.
27 Correct 667 ms 142552 KB Correct.
28 Correct 694 ms 142560 KB Correct.
29 Execution timed out 1075 ms 141468 KB Time limit exceeded
30 Halted 0 ms 0 KB -