oj.uz

Submission #546909

# Submission time Handle Problem Language Result Execution time Memory
546909 2022-04-08T20:29:03 Z Ooops_sorry Arranging Tickets (JOI17_arranging_tickets) C++14
100 / 100
 5455 ms 39684 KB 
#include<bits/stdc++.h>

using namespace std;

#define int long long
#define pb push_back
#define ld double
#define ll __int128

mt19937 rnd(51);

const int INF = 1e14 + 100;

struct st {
    vector<int> t, add, arr;
    void build(int v, int l, int r) {
        if (l == r) {
            t[v] = arr[l];
            return;
        }
        int m = (l + r) / 2;
        build(2 * v, l, m), build(2 * v + 1, m + 1, r);
    }
    st(vector<int> a) {
        int n = a.size();
        arr = a;
        t.resize(4 * n);
        add.resize(4 * n);
        build(1, 0, n - 1);
    }
    void push(int v) {
        t[v] += add[v];
        if (v * 2 < add.size()) {
            add[v * 2] += add[v];
            add[v * 2 + 1] += add[v];
        }
        add[v] = 0;
    }
    void update(int v, int tl, int tr, int l, int r, int val) {
        if (l > r) return;
        if (tl == l && tr == r) {
            add[v] += val;
            return;
        }
        int tm = (tl + tr) / 2;
        update(2 * v, tl, tm, l, min(r, tm), val), update(2 * v + 1, tm + 1, tr, max(l, tm + 1), r, val);
    }
    int get(int v, int l, int r, int pos) {
        push(v);
        if (l == r) {
            return t[v];
        }
        int m = (l + r) / 2;
        if (pos <= m) {
            return get(2 * v, l, m, pos);
        } else {
            return get(2 * v + 1, m + 1, r, pos);
        }
    }
};

signed main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif // LOCAL
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, q;
    cin >> n >> q;
    vector<int> a(q), b(q), c(q), pr(n + 1), d(n);
    vector<vector<pair<int,int>>> need(n);
    for (int i = 0; i < q; i++) {
        cin >> a[i] >> b[i] >> c[i];
        a[i]--, b[i]--;
        if (a[i] > b[i]) swap(a[i], b[i]);
        b[i]--;
        pr[a[i]] += c[i], pr[b[i] + 1] -= c[i];
        need[a[i]].pb({b[i], c[i]});
    }
    int sum = 0;
    for (int i = 0; i < n; i++) {
        sum += pr[i];
        d[i] = sum;
    }
    int l = 0, r = INF;
    int val = *max_element(d.begin(), d.end());
    while (r - l > 1) {
        int mid = (r + l) / 2;
        bool ok = 0, bad = 0;
        if (val <= mid) {
            r = mid;
            continue;
        }
        for (int m = val - mid; m <= val - mid + 1; m++) {
            for (int j = 0; j < n; j++) {
                d[j] += m;
            }
            st t(d);
            for (int j = 0; j < n; j++) {
                d[j] -= m;
            }
            multiset<pair<int,int>> st;
            int cnt = 0;
            for (int i = 0; i < n; i++) {
                for (auto to : need[i]) {
                    st.insert(to);
                }
                int val = t.get(1, 0, n - 1, i);
                while (val > mid) {
                    if (st.size() == 0) {
                        bad = 1;
                        break;
                    }
                    auto to = *st.rbegin();
                    st.erase(st.find(to));
                    if (2 * to.second >= val - mid) {
                        int need = (val - mid + 1) / 2;
                        t.update(1, 0, n - 1, i, to.first, -2 * need);
                        to.second -= need;
                        if (to.second > 0) {
                            st.insert(to);
                        }
                        cnt += need;
                        break;
                    } else {
                        t.update(1, 0, n - 1, i, to.first, -2 * to.second);
                        cnt += to.second;
                        val -= 2 * to.second;
                    }
                }
                if (bad) {
                    break;
                }
            }
            if (cnt <= m && !bad) {
                ok = 1;
                break;
            }
        }
        if (ok) {
            r = mid;
        } else {
            l = mid;
        }
    }
    cout << r << endl;
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 328 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 328 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 328 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 328 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 328 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 328 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 324 KB Output is correct
17 Correct 1 ms 328 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 2 ms 340 KB Output is correct
21 Correct 2 ms 340 KB Output is correct
22 Correct 1 ms 332 KB Output is correct
23 Correct 2 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 328 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 1 ms 340 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 328 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 328 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 328 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 324 KB Output is correct
17 Correct 1 ms 328 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 2 ms 340 KB Output is correct
21 Correct 2 ms 340 KB Output is correct
22 Correct 1 ms 332 KB Output is correct
23 Correct 2 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 328 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 8 ms 980 KB Output is correct
29 Correct 9 ms 972 KB Output is correct
30 Correct 8 ms 956 KB Output is correct
31 Correct 11 ms 1036 KB Output is correct
32 Correct 13 ms 852 KB Output is correct
33 Correct 9 ms 980 KB Output is correct
34 Correct 8 ms 852 KB Output is correct
35 Correct 10 ms 852 KB Output is correct
36 Correct 9 ms 980 KB Output is correct
37 Correct 7 ms 956 KB Output is correct
38 Correct 5 ms 980 KB Output is correct
39 Correct 7 ms 976 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 328 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 328 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 328 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 324 KB Output is correct
17 Correct 1 ms 328 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 2 ms 340 KB Output is correct
21 Correct 2 ms 340 KB Output is correct
22 Correct 1 ms 332 KB Output is correct
23 Correct 2 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 328 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 8 ms 980 KB Output is correct
29 Correct 9 ms 972 KB Output is correct
30 Correct 8 ms 956 KB Output is correct
31 Correct 11 ms 1036 KB Output is correct
32 Correct 13 ms 852 KB Output is correct
33 Correct 9 ms 980 KB Output is correct
34 Correct 8 ms 852 KB Output is correct
35 Correct 10 ms 852 KB Output is correct
36 Correct 9 ms 980 KB Output is correct
37 Correct 7 ms 956 KB Output is correct
38 Correct 5 ms 980 KB Output is correct
39 Correct 7 ms 976 KB Output is correct
40 Correct 1008 ms 38700 KB Output is correct
41 Correct 845 ms 38448 KB Output is correct
42 Correct 705 ms 38540 KB Output is correct
43 Correct 1194 ms 38172 KB Output is correct
44 Correct 1258 ms 38488 KB Output is correct
45 Correct 1568 ms 32608 KB Output is correct
46 Correct 811 ms 37656 KB Output is correct
47 Correct 483 ms 31572 KB Output is correct
48 Correct 654 ms 37744 KB Output is correct
49 Correct 383 ms 24852 KB Output is correct
50 Correct 456 ms 26980 KB Output is correct
51 Correct 379 ms 25344 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 328 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 328 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 328 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 324 KB Output is correct
17 Correct 1 ms 328 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 2 ms 340 KB Output is correct
21 Correct 2 ms 340 KB Output is correct
22 Correct 1 ms 332 KB Output is correct
23 Correct 2 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 328 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 8 ms 980 KB Output is correct
29 Correct 9 ms 972 KB Output is correct
30 Correct 8 ms 956 KB Output is correct
31 Correct 11 ms 1036 KB Output is correct
32 Correct 13 ms 852 KB Output is correct
33 Correct 9 ms 980 KB Output is correct
34 Correct 8 ms 852 KB Output is correct
35 Correct 10 ms 852 KB Output is correct
36 Correct 9 ms 980 KB Output is correct
37 Correct 7 ms 956 KB Output is correct
38 Correct 5 ms 980 KB Output is correct
39 Correct 7 ms 976 KB Output is correct
40 Correct 1008 ms 38700 KB Output is correct
41 Correct 845 ms 38448 KB Output is correct
42 Correct 705 ms 38540 KB Output is correct
43 Correct 1194 ms 38172 KB Output is correct
44 Correct 1258 ms 38488 KB Output is correct
45 Correct 1568 ms 32608 KB Output is correct
46 Correct 811 ms 37656 KB Output is correct
47 Correct 483 ms 31572 KB Output is correct
48 Correct 654 ms 37744 KB Output is correct
49 Correct 383 ms 24852 KB Output is correct
50 Correct 456 ms 26980 KB Output is correct
51 Correct 379 ms 25344 KB Output is correct
52 Correct 4749 ms 39488 KB Output is correct
53 Correct 1874 ms 39216 KB Output is correct
54 Correct 4764 ms 39288 KB Output is correct
55 Correct 5455 ms 39684 KB Output is correct
56 Correct 4935 ms 39556 KB Output is correct
57 Correct 4360 ms 38308 KB Output is correct
58 Correct 4319 ms 38692 KB Output is correct
59 Correct 2272 ms 22608 KB Output is correct