oj.uz

Submission #1104263

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

using namespace std;
typedef long long ll;

const int N = 2e5 + 12;

struct bit{
    vector<ll> t;
    int n;
    void init(int s) {
        n = s;
        t.assign(n + 1, 0);
    }
    void upd(int pos, ll val) {
        while(pos <= n) {
            t[pos] += val;
            pos += pos & -pos;    
        }
    }
    ll get(int i) {
        ll res = 0;
        while(i) {
            res += t[i];
            i -= i & -i;
        }
        return res;
    }
    ll get(int l, int r) {
        return get(r) - get(l - 1);
    }
}T;

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++;
        }
        while(ti < w && f[ti].second < a[i]) {
            col++;
            T.upd(find(f[ti].first), 1);
            ti++;
        }
        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++) {
        vt.push_back(L[i]);
        vt.push_back(R[i]);
        f.emplace_back(L[i], R[i]);
        rs.push_back(R[i]);
        ls.push_back(L[i]);
    }
    for(int i = 0; i < m; i++) {
        vt.push_back(a[i]);
        vt.push_back(b[i]);
    }
    vt.push_back(0);
    sort(vt.begin(), vt.end());
    vt.resize(unique(vt.begin(), vt.end()) - vt.begin());
    T.init((int)vt.size());
    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:89:9: warning: unused variable 'ret' [-Wunused-variable]
   89 |     int ret = 0, ret1 = 0;
      |         ^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 137792 KB Correct.
2 Correct 105 ms 137800 KB Correct.
3 Correct 99 ms 137800 KB Correct.
4 Correct 91 ms 137800 KB Correct.
5 Correct 93 ms 137800 KB Correct.
6 Correct 90 ms 137872 KB Correct.
7 Correct 85 ms 137800 KB Correct.

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 147660 KB Correct.
2 Correct 189 ms 148684 KB Correct.
3 Correct 97 ms 137800 KB Correct.
4 Correct 104 ms 138824 KB Correct.
5 Correct 86 ms 137800 KB Correct.
6 Correct 193 ms 147356 KB Correct.
7 Correct 83 ms 137692 KB Correct.
8 Correct 171 ms 147868 KB Correct.
9 Correct 177 ms 148636 KB Correct.

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 147660 KB Correct.
2 Correct 189 ms 148684 KB Correct.
3 Correct 97 ms 137800 KB Correct.
4 Correct 104 ms 138824 KB Correct.
5 Correct 86 ms 137800 KB Correct.
6 Correct 193 ms 147356 KB Correct.
7 Correct 83 ms 137692 KB Correct.
8 Correct 171 ms 147868 KB Correct.
9 Correct 177 ms 148636 KB Correct.
10 Correct 873 ms 215284 KB Correct.
11 Correct 573 ms 216212 KB Correct.
12 Correct 88 ms 138824 KB Correct.
13 Correct 101 ms 137800 KB Correct.
14 Correct 961 ms 215188 KB Correct.
15 Correct 634 ms 216372 KB Correct.
16 Correct 999 ms 215192 KB Correct.
17 Correct 677 ms 216884 KB Correct.

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 137792 KB Correct.
2 Correct 105 ms 137800 KB Correct.
3 Correct 99 ms 137800 KB Correct.
4 Correct 91 ms 137800 KB Correct.
5 Correct 93 ms 137800 KB Correct.
6 Correct 90 ms 137872 KB Correct.
7 Correct 85 ms 137800 KB Correct.
8 Correct 209 ms 147660 KB Correct.
9 Correct 189 ms 148684 KB Correct.
10 Correct 97 ms 137800 KB Correct.
11 Correct 104 ms 138824 KB Correct.
12 Correct 86 ms 137800 KB Correct.
13 Correct 193 ms 147356 KB Correct.
14 Correct 83 ms 137692 KB Correct.
15 Correct 171 ms 147868 KB Correct.
16 Correct 177 ms 148636 KB Correct.
17 Correct 873 ms 215284 KB Correct.
18 Correct 573 ms 216212 KB Correct.
19 Correct 88 ms 138824 KB Correct.
20 Correct 101 ms 137800 KB Correct.
21 Correct 961 ms 215188 KB Correct.
22 Correct 634 ms 216372 KB Correct.
23 Correct 999 ms 215192 KB Correct.
24 Correct 677 ms 216884 KB Correct.
25 Correct 755 ms 216212 KB Correct.
26 Correct 780 ms 216552 KB Correct.
27 Correct 754 ms 216372 KB Correct.
28 Correct 814 ms 216368 KB Correct.
29 Execution timed out 1064 ms 215204 KB Time limit exceeded
30 Halted 0 ms 0 KB -