oj.uz

Submission #1104265

# Submission time Handle Problem Language Result Execution time Memory
1104265 2024-10-23T11:07:02 Z _8_8_ Train (APIO24_train) C++17
40 / 100
 1000 ms 211872 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;
    }
    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:64:9: warning: unused variable 'ret' [-Wunused-variable]
   64 |     int ret = 0, ret1 = 0;
      |         ^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 137800 KB Correct.
2 Correct 91 ms 137800 KB Correct.
3 Correct 90 ms 137808 KB Correct.
4 Correct 93 ms 137800 KB Correct.
5 Correct 78 ms 137708 KB Correct.
6 Correct 94 ms 137824 KB Correct.
7 Correct 97 ms 137804 KB Correct.

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 145188 KB Correct.
2 Correct 164 ms 146276 KB Correct.
3 Correct 87 ms 137800 KB Correct.
4 Correct 96 ms 138888 KB Correct.
5 Correct 97 ms 137876 KB Correct.
6 Correct 191 ms 145056 KB Correct.
7 Correct 92 ms 137800 KB Correct.
8 Correct 162 ms 146336 KB Correct.
9 Correct 193 ms 146336 KB Correct.

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 145188 KB Correct.
2 Correct 164 ms 146276 KB Correct.
3 Correct 87 ms 137800 KB Correct.
4 Correct 96 ms 138888 KB Correct.
5 Correct 97 ms 137876 KB Correct.
6 Correct 191 ms 145056 KB Correct.
7 Correct 92 ms 137800 KB Correct.
8 Correct 162 ms 146336 KB Correct.
9 Correct 193 ms 146336 KB Correct.
10 Correct 957 ms 210236 KB Correct.
11 Correct 581 ms 211100 KB Correct.
12 Correct 101 ms 139008 KB Correct.
13 Correct 88 ms 137812 KB Correct.
14 Correct 855 ms 210100 KB Correct.
15 Correct 540 ms 211100 KB Correct.
16 Correct 892 ms 210124 KB Correct.
17 Correct 618 ms 211872 KB Correct.

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 137800 KB Correct.
2 Correct 91 ms 137800 KB Correct.
3 Correct 90 ms 137808 KB Correct.
4 Correct 93 ms 137800 KB Correct.
5 Correct 78 ms 137708 KB Correct.
6 Correct 94 ms 137824 KB Correct.
7 Correct 97 ms 137804 KB Correct.
8 Correct 183 ms 145188 KB Correct.
9 Correct 164 ms 146276 KB Correct.
10 Correct 87 ms 137800 KB Correct.
11 Correct 96 ms 138888 KB Correct.
12 Correct 97 ms 137876 KB Correct.
13 Correct 191 ms 145056 KB Correct.
14 Correct 92 ms 137800 KB Correct.
15 Correct 162 ms 146336 KB Correct.
16 Correct 193 ms 146336 KB Correct.
17 Correct 957 ms 210236 KB Correct.
18 Correct 581 ms 211100 KB Correct.
19 Correct 101 ms 139008 KB Correct.
20 Correct 88 ms 137812 KB Correct.
21 Correct 855 ms 210100 KB Correct.
22 Correct 540 ms 211100 KB Correct.
23 Correct 892 ms 210124 KB Correct.
24 Correct 618 ms 211872 KB Correct.
25 Correct 685 ms 211276 KB Correct.
26 Correct 717 ms 211100 KB Correct.
27 Correct 726 ms 211196 KB Correct.
28 Correct 731 ms 211104 KB Correct.
29 Execution timed out 1071 ms 210076 KB Time limit exceeded
30 Halted 0 ms 0 KB -