oj.uz

Submission #1104262

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

using namespace std;
typedef long long ll;

const int N = 1e5 + 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]);
    }
    // for(int i = 0; i < w; i++) {
    //     if(f[i].first > L && f[i].second < R) {
    //         ret++;
    //     }
    // }
    // if(ret != ret1) cout << ret << ' ' << ret1 << '\n';
    return ret1;
    // assert(L <= R);
    // return ti - T.get(find(L));
}
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;
    // cout << pos << ' ' << d[v][0].v << "x\n";
    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]);
            // if(j == 6) {
            //     cout << y[j] << " " << dp[j] << ' ' << b[j] << '\n';
            // }
            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 50 ms 68424 KB Correct.
2 Correct 47 ms 68428 KB Correct.
3 Correct 47 ms 68440 KB Correct.
4 Correct 48 ms 68424 KB Correct.
5 Correct 46 ms 68168 KB Correct.
6 Correct 46 ms 68176 KB Correct.
7 Correct 47 ms 68176 KB Correct.

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 79516 KB Correct.
2 Correct 156 ms 79068 KB Correct.
3 Correct 61 ms 68168 KB Correct.
4 Correct 55 ms 70004 KB Correct.
5 Correct 48 ms 68168 KB Correct.
6 Correct 147 ms 77980 KB Correct.
7 Correct 44 ms 68168 KB Correct.
8 Correct 134 ms 78240 KB Correct.
9 Correct 162 ms 83928 KB Correct.

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 79516 KB Correct.
2 Correct 156 ms 79068 KB Correct.
3 Correct 61 ms 68168 KB Correct.
4 Correct 55 ms 70004 KB Correct.
5 Correct 48 ms 68168 KB Correct.
6 Correct 147 ms 77980 KB Correct.
7 Correct 44 ms 68168 KB Correct.
8 Correct 134 ms 78240 KB Correct.
9 Correct 162 ms 83928 KB Correct.
10 Correct 975 ms 151956 KB Correct.
11 Correct 588 ms 153748 KB Correct.
12 Correct 56 ms 69448 KB Correct.
13 Correct 54 ms 68316 KB Correct.
14 Correct 986 ms 150940 KB Correct.
15 Correct 613 ms 154516 KB Correct.
16 Correct 964 ms 151876 KB Correct.
17 Correct 663 ms 154004 KB Correct.

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 68424 KB Correct.
2 Correct 47 ms 68428 KB Correct.
3 Correct 47 ms 68440 KB Correct.
4 Correct 48 ms 68424 KB Correct.
5 Correct 46 ms 68168 KB Correct.
6 Correct 46 ms 68176 KB Correct.
7 Correct 47 ms 68176 KB Correct.
8 Correct 161 ms 79516 KB Correct.
9 Correct 156 ms 79068 KB Correct.
10 Correct 61 ms 68168 KB Correct.
11 Correct 55 ms 70004 KB Correct.
12 Correct 48 ms 68168 KB Correct.
13 Correct 147 ms 77980 KB Correct.
14 Correct 44 ms 68168 KB Correct.
15 Correct 134 ms 78240 KB Correct.
16 Correct 162 ms 83928 KB Correct.
17 Correct 975 ms 151956 KB Correct.
18 Correct 588 ms 153748 KB Correct.
19 Correct 56 ms 69448 KB Correct.
20 Correct 54 ms 68316 KB Correct.
21 Correct 986 ms 150940 KB Correct.
22 Correct 613 ms 154516 KB Correct.
23 Correct 964 ms 151876 KB Correct.
24 Correct 663 ms 154004 KB Correct.
25 Correct 652 ms 154576 KB Correct.
26 Correct 618 ms 154568 KB Correct.
27 Correct 645 ms 154516 KB Correct.
28 Correct 667 ms 154540 KB Correct.
29 Execution timed out 1072 ms 152388 KB Time limit exceeded
30 Halted 0 ms 0 KB -