oj.uz

Submission #1104266

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

using namespace std;
typedef long long ll;

const int N = 2e5 + 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;
    }
};
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 = w) {
    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 = w ) {
    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;
int find(int pos) {
    int it = lower_bound(vt.begin(), vt.end(), pos) - vt.begin() + 1;
    return it;
}
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 = w) {
    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());
    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:63:9: warning: unused variable 'ret' [-Wunused-variable]
   63 |     int ret = 0, ret1 = 0;
      |         ^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 137804 KB Correct.
2 Correct 91 ms 137772 KB Correct.
3 Correct 98 ms 137808 KB Correct.
4 Correct 96 ms 137832 KB Correct.
5 Correct 97 ms 137756 KB Correct.
6 Correct 97 ms 137800 KB Correct.
7 Correct 92 ms 137800 KB Correct.

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 145252 KB Correct.
2 Correct 168 ms 146360 KB Correct.
3 Correct 85 ms 137664 KB Correct.
4 Correct 97 ms 138828 KB Correct.
5 Correct 90 ms 137800 KB Correct.
6 Correct 165 ms 144948 KB Correct.
7 Correct 95 ms 137712 KB Correct.
8 Correct 140 ms 146352 KB Correct.
9 Correct 157 ms 146316 KB Correct.

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 145252 KB Correct.
2 Correct 168 ms 146360 KB Correct.
3 Correct 85 ms 137664 KB Correct.
4 Correct 97 ms 138828 KB Correct.
5 Correct 90 ms 137800 KB Correct.
6 Correct 165 ms 144948 KB Correct.
7 Correct 95 ms 137712 KB Correct.
8 Correct 140 ms 146352 KB Correct.
9 Correct 157 ms 146316 KB Correct.
10 Correct 817 ms 210264 KB Correct.
11 Correct 531 ms 211168 KB Correct.
12 Correct 83 ms 138828 KB Correct.
13 Correct 79 ms 137800 KB Correct.
14 Correct 583 ms 210036 KB Correct.
15 Correct 517 ms 211100 KB Correct.
16 Correct 664 ms 210076 KB Correct.
17 Correct 523 ms 211896 KB Correct.

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 137804 KB Correct.
2 Correct 91 ms 137772 KB Correct.
3 Correct 98 ms 137808 KB Correct.
4 Correct 96 ms 137832 KB Correct.
5 Correct 97 ms 137756 KB Correct.
6 Correct 97 ms 137800 KB Correct.
7 Correct 92 ms 137800 KB Correct.
8 Correct 156 ms 145252 KB Correct.
9 Correct 168 ms 146360 KB Correct.
10 Correct 85 ms 137664 KB Correct.
11 Correct 97 ms 138828 KB Correct.
12 Correct 90 ms 137800 KB Correct.
13 Correct 165 ms 144948 KB Correct.
14 Correct 95 ms 137712 KB Correct.
15 Correct 140 ms 146352 KB Correct.
16 Correct 157 ms 146316 KB Correct.
17 Correct 817 ms 210264 KB Correct.
18 Correct 531 ms 211168 KB Correct.
19 Correct 83 ms 138828 KB Correct.
20 Correct 79 ms 137800 KB Correct.
21 Correct 583 ms 210036 KB Correct.
22 Correct 517 ms 211100 KB Correct.
23 Correct 664 ms 210076 KB Correct.
24 Correct 523 ms 211896 KB Correct.
25 Correct 737 ms 215196 KB Correct.
26 Correct 718 ms 211224 KB Correct.
27 Correct 699 ms 215136 KB Correct.
28 Correct 680 ms 215140 KB Correct.
29 Execution timed out 1056 ms 210072 KB Time limit exceeded
30 Halted 0 ms 0 KB -