oj.uz

Submission #366996

# Submission time Handle Problem Language Result Execution time Memory
366996 2021-02-16T02:27:55 Z fishy15 Arranging Tickets (JOI17_arranging_tickets) C++14
10 / 100
 6000 ms 6784 KB 
#include <iostream>
#include <iomanip>
#include <fstream>
#include <vector>
#include <array>
#include <algorithm>
#include <utility>
#include <map>
#include <queue>
#include <set>
#include <cmath>
#include <cstdio>
#include <cstring>

#define ll long long
#define ld long double
#define eps 1e-8
#define MOD 1000000007

#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3f

// change if necessary
#define MAXN 200010

using namespace std;

int n, m;
vector<array<int, 3>> range[MAXN];
ll init[MAXN];
int min_check, max_check;

struct cmp {
    bool operator()(const array<int, 3> &a, const array<int, 3> &b) const {
        if (a[1] == b[1]) {
            if (a[0] == b[0]) {
                return a[2] < b[2];
            }
            return a[0] < b[0];
        }
        return a[1] < b[1];
    }
};

struct bit {
    ll vals[MAXN];
    void reset() {
        memset(vals, 0, sizeof vals);
        for (int i = 0; i < n; i++) {
            ll x = init[i];
            if (i) x -= init[i - 1];
            upd(i, x);
        }
    }
    void upd(int x, ll v) {
        x++;
        while (x < MAXN) {
            vals[x] += v;
            x += x & -x;
        }
    }
    void upd(int l, int r, ll v) {
        upd(l, v);
        upd(r, -v);
    }
    ll qry(int x) {
        x++;
        ll res = 0;
        while (x) {
            res += vals[x];
            x -= x & -x;
        }
        return res;
    }
} b;

ll check(ll m, ll n, ll t) {
    b.reset();
    multiset<array<int, 3>, cmp> cur;
    for (int i = 0; i <= t; i++) {
        ll need_rem = (b.qry(i) + n - m + 1) / 2;
        n -= need_rem;
        for (auto &arr : range[i]) {
            if (arr[1] >= t) {
                cur.insert(arr);
            }
        }
        while (need_rem) {
            if (cur.empty()) {
                return false;
            }
            auto t = *cur.rbegin();
            cur.erase(cur.find(t));
            ll to_rem = min<ll>(t[2], need_rem);
            b.upd(0, t[0], to_rem);
            b.upd(t[0], t[1], -to_rem);
            b.upd(t[1], ::n, to_rem);
            t[2] -= to_rem;
            need_rem -= to_rem;
            if (t[2]) cur.insert(t);
        }
    }

    for (int i = 0; i < ::n; i++) {
        if (b.qry(i) > m) {
            return false;
        }
    }

    return true;
}

ll check(ll m) {
    ll a = init[min_check];
    for (int i = 0; i <= ::m; i++) {
        for (int j = 0; j < n; j++) {
            if (check(m, i, j)) return true;
        }
    }

    return false;
    /* return check(m, a - m, min_check) || check(m, a - m + 1, min_check) */
        /* || check(m, a - m, max_check) || check(m, a - m + 1, max_check); */
}

int main() {
    cin.tie(0)->sync_with_stdio(0);

    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a, b, c; cin >> a >> b >> c;
        a--; b--;
        if (a > b) swap(a, b);
        init[a] += c;
        init[b] -= c;
        range[a].push_back({a, b, c});
    }

    for (int i = 1; i < n; i++) {
        init[i] += init[i - 1];
    }

    for (int i = 0; i < n; i++) {
        if (init[i] > init[min_check]) {
            min_check = i;
            max_check = i;
        } else if (init[i] == init[min_check]) {
            max_check = i;
        }
    }

    ll l = 0;
    ll r = init[min_check];
    ll ans = init[min_check];

    while (l <= r) {
        ll m = (l + r) / 2;
        if (check(m)) {
            ans = m;
            r = m - 1;
        } else {
            l = m + 1;
        }
    }

    cout << ans << '\n';

    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 6636 KB Output is correct
2 Correct 53 ms 6656 KB Output is correct
3 Correct 38 ms 6764 KB Output is correct
4 Correct 44 ms 6764 KB Output is correct
5 Correct 56 ms 6636 KB Output is correct
6 Correct 53 ms 6636 KB Output is correct
7 Correct 59 ms 6764 KB Output is correct
8 Correct 59 ms 6784 KB Output is correct
9 Correct 55 ms 6764 KB Output is correct
10 Correct 58 ms 6636 KB Output is correct
11 Correct 58 ms 6636 KB Output is correct
12 Correct 47 ms 6664 KB Output is correct
13 Correct 59 ms 6636 KB Output is correct
14 Correct 125 ms 6764 KB Output is correct
15 Correct 78 ms 6636 KB Output is correct

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 6636 KB Output is correct
2 Correct 53 ms 6656 KB Output is correct
3 Correct 38 ms 6764 KB Output is correct
4 Correct 44 ms 6764 KB Output is correct
5 Correct 56 ms 6636 KB Output is correct
6 Correct 53 ms 6636 KB Output is correct
7 Correct 59 ms 6764 KB Output is correct
8 Correct 59 ms 6784 KB Output is correct
9 Correct 55 ms 6764 KB Output is correct
10 Correct 58 ms 6636 KB Output is correct
11 Correct 58 ms 6636 KB Output is correct
12 Correct 47 ms 6664 KB Output is correct
13 Correct 59 ms 6636 KB Output is correct
14 Correct 125 ms 6764 KB Output is correct
15 Correct 78 ms 6636 KB Output is correct
16 Execution timed out 6013 ms 6680 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 6636 KB Output is correct
2 Correct 53 ms 6656 KB Output is correct
3 Correct 38 ms 6764 KB Output is correct
4 Correct 44 ms 6764 KB Output is correct
5 Correct 56 ms 6636 KB Output is correct
6 Correct 53 ms 6636 KB Output is correct
7 Correct 59 ms 6764 KB Output is correct
8 Correct 59 ms 6784 KB Output is correct
9 Correct 55 ms 6764 KB Output is correct
10 Correct 58 ms 6636 KB Output is correct
11 Correct 58 ms 6636 KB Output is correct
12 Correct 47 ms 6664 KB Output is correct
13 Correct 59 ms 6636 KB Output is correct
14 Correct 125 ms 6764 KB Output is correct
15 Correct 78 ms 6636 KB Output is correct
16 Execution timed out 6013 ms 6680 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 6636 KB Output is correct
2 Correct 53 ms 6656 KB Output is correct
3 Correct 38 ms 6764 KB Output is correct
4 Correct 44 ms 6764 KB Output is correct
5 Correct 56 ms 6636 KB Output is correct
6 Correct 53 ms 6636 KB Output is correct
7 Correct 59 ms 6764 KB Output is correct
8 Correct 59 ms 6784 KB Output is correct
9 Correct 55 ms 6764 KB Output is correct
10 Correct 58 ms 6636 KB Output is correct
11 Correct 58 ms 6636 KB Output is correct
12 Correct 47 ms 6664 KB Output is correct
13 Correct 59 ms 6636 KB Output is correct
14 Correct 125 ms 6764 KB Output is correct
15 Correct 78 ms 6636 KB Output is correct
16 Execution timed out 6013 ms 6680 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 6636 KB Output is correct
2 Correct 53 ms 6656 KB Output is correct
3 Correct 38 ms 6764 KB Output is correct
4 Correct 44 ms 6764 KB Output is correct
5 Correct 56 ms 6636 KB Output is correct
6 Correct 53 ms 6636 KB Output is correct
7 Correct 59 ms 6764 KB Output is correct
8 Correct 59 ms 6784 KB Output is correct
9 Correct 55 ms 6764 KB Output is correct
10 Correct 58 ms 6636 KB Output is correct
11 Correct 58 ms 6636 KB Output is correct
12 Correct 47 ms 6664 KB Output is correct
13 Correct 59 ms 6636 KB Output is correct
14 Correct 125 ms 6764 KB Output is correct
15 Correct 78 ms 6636 KB Output is correct
16 Execution timed out 6013 ms 6680 KB Time limit exceeded
17 Halted 0 ms 0 KB -