oj.uz

Submission #1104273

# Submission time Handle Problem Language Result Execution time Memory
1104273 2024-10-23T11:20:02 Z _8_8_ Train (APIO24_train) C++17
40 / 100
 1000 ms 140944 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.swap(_T);
    x.swap(X);
    y.swap(Y);
    a.swap(A);
    b.swap(B);
    c.swap(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 48 ms 68292 KB Correct.
2 Correct 49 ms 68284 KB Correct.
3 Correct 42 ms 68440 KB Correct.
4 Correct 42 ms 68408 KB Correct.
5 Correct 42 ms 68172 KB Correct.
6 Correct 41 ms 68176 KB Correct.
7 Correct 38 ms 68356 KB Correct.

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 73644 KB Correct.
2 Correct 127 ms 74400 KB Correct.
3 Correct 52 ms 68376 KB Correct.
4 Correct 47 ms 68936 KB Correct.
5 Correct 41 ms 68176 KB Correct.
6 Correct 113 ms 73600 KB Correct.
7 Correct 40 ms 68176 KB Correct.
8 Correct 84 ms 74404 KB Correct.
9 Correct 112 ms 74408 KB Correct.

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 73644 KB Correct.
2 Correct 127 ms 74400 KB Correct.
3 Correct 52 ms 68376 KB Correct.
4 Correct 47 ms 68936 KB Correct.
5 Correct 41 ms 68176 KB Correct.
6 Correct 113 ms 73600 KB Correct.
7 Correct 40 ms 68176 KB Correct.
8 Correct 84 ms 74404 KB Correct.
9 Correct 112 ms 74408 KB Correct.
10 Correct 909 ms 139424 KB Correct.
11 Correct 542 ms 140208 KB Correct.
12 Correct 54 ms 69140 KB Correct.
13 Correct 48 ms 68340 KB Correct.
14 Correct 607 ms 139164 KB Correct.
15 Correct 542 ms 140188 KB Correct.
16 Correct 710 ms 139404 KB Correct.
17 Correct 476 ms 140944 KB Correct.

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 68292 KB Correct.
2 Correct 49 ms 68284 KB Correct.
3 Correct 42 ms 68440 KB Correct.
4 Correct 42 ms 68408 KB Correct.
5 Correct 42 ms 68172 KB Correct.
6 Correct 41 ms 68176 KB Correct.
7 Correct 38 ms 68356 KB Correct.
8 Correct 123 ms 73644 KB Correct.
9 Correct 127 ms 74400 KB Correct.
10 Correct 52 ms 68376 KB Correct.
11 Correct 47 ms 68936 KB Correct.
12 Correct 41 ms 68176 KB Correct.
13 Correct 113 ms 73600 KB Correct.
14 Correct 40 ms 68176 KB Correct.
15 Correct 84 ms 74404 KB Correct.
16 Correct 112 ms 74408 KB Correct.
17 Correct 909 ms 139424 KB Correct.
18 Correct 542 ms 140208 KB Correct.
19 Correct 54 ms 69140 KB Correct.
20 Correct 48 ms 68340 KB Correct.
21 Correct 607 ms 139164 KB Correct.
22 Correct 542 ms 140188 KB Correct.
23 Correct 710 ms 139404 KB Correct.
24 Correct 476 ms 140944 KB Correct.
25 Correct 637 ms 139944 KB Correct.
26 Correct 656 ms 140192 KB Correct.
27 Correct 697 ms 140444 KB Correct.
28 Correct 696 ms 140204 KB Correct.
29 Execution timed out 1046 ms 139356 KB Time limit exceeded
30 Halted 0 ms 0 KB -