oj.uz

Submission #1104274

# Submission time Handle Problem Language Result Execution time Memory
1104274 2024-10-23T11:23:13 Z _8_8_ Train (APIO24_train) C++17
40 / 100
 1000 ms 140864 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;
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 47 ms 68428 KB Correct.
2 Correct 47 ms 68428 KB Correct.
3 Correct 52 ms 68424 KB Correct.
4 Correct 46 ms 68240 KB Correct.
5 Correct 43 ms 68168 KB Correct.
6 Correct 46 ms 68352 KB Correct.
7 Correct 46 ms 68168 KB Correct.

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 73632 KB Correct.
2 Correct 139 ms 74320 KB Correct.
3 Correct 48 ms 68168 KB Correct.
4 Correct 55 ms 68936 KB Correct.
5 Correct 47 ms 68268 KB Correct.
6 Correct 110 ms 73548 KB Correct.
7 Correct 46 ms 68168 KB Correct.
8 Correct 98 ms 74308 KB Correct.
9 Correct 132 ms 74400 KB Correct.

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 73632 KB Correct.
2 Correct 139 ms 74320 KB Correct.
3 Correct 48 ms 68168 KB Correct.
4 Correct 55 ms 68936 KB Correct.
5 Correct 47 ms 68268 KB Correct.
6 Correct 110 ms 73548 KB Correct.
7 Correct 46 ms 68168 KB Correct.
8 Correct 98 ms 74308 KB Correct.
9 Correct 132 ms 74400 KB Correct.
10 Correct 898 ms 139508 KB Correct.
11 Correct 546 ms 140188 KB Correct.
12 Correct 56 ms 68936 KB Correct.
13 Correct 46 ms 68328 KB Correct.
14 Correct 606 ms 139320 KB Correct.
15 Correct 560 ms 140132 KB Correct.
16 Correct 681 ms 139212 KB Correct.
17 Correct 417 ms 140864 KB Correct.

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 68428 KB Correct.
2 Correct 47 ms 68428 KB Correct.
3 Correct 52 ms 68424 KB Correct.
4 Correct 46 ms 68240 KB Correct.
5 Correct 43 ms 68168 KB Correct.
6 Correct 46 ms 68352 KB Correct.
7 Correct 46 ms 68168 KB Correct.
8 Correct 118 ms 73632 KB Correct.
9 Correct 139 ms 74320 KB Correct.
10 Correct 48 ms 68168 KB Correct.
11 Correct 55 ms 68936 KB Correct.
12 Correct 47 ms 68268 KB Correct.
13 Correct 110 ms 73548 KB Correct.
14 Correct 46 ms 68168 KB Correct.
15 Correct 98 ms 74308 KB Correct.
16 Correct 132 ms 74400 KB Correct.
17 Correct 898 ms 139508 KB Correct.
18 Correct 546 ms 140188 KB Correct.
19 Correct 56 ms 68936 KB Correct.
20 Correct 46 ms 68328 KB Correct.
21 Correct 606 ms 139320 KB Correct.
22 Correct 560 ms 140132 KB Correct.
23 Correct 681 ms 139212 KB Correct.
24 Correct 417 ms 140864 KB Correct.
25 Correct 583 ms 140188 KB Correct.
26 Correct 585 ms 140188 KB Correct.
27 Correct 606 ms 140448 KB Correct.
28 Correct 688 ms 140140 KB Correct.
29 Execution timed out 1073 ms 139288 KB Time limit exceeded
30 Halted 0 ms 0 KB -