oj.uz

Submission #366997

# Submission time Handle Problem Language Result Execution time Memory
366997 2021-02-16T02:29:15 Z fishy15 Arranging Tickets (JOI17_arranging_tickets) C++14
10 / 100
 6000 ms 6764 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 67 ms 6636 KB Output is correct
2 Correct 54 ms 6636 KB Output is correct
3 Correct 35 ms 6636 KB Output is correct
4 Correct 45 ms 6764 KB Output is correct
5 Correct 57 ms 6764 KB Output is correct
6 Correct 63 ms 6636 KB Output is correct
7 Correct 61 ms 6636 KB Output is correct
8 Correct 59 ms 6636 KB Output is correct
9 Correct 51 ms 6636 KB Output is correct
10 Correct 59 ms 6660 KB Output is correct
11 Correct 60 ms 6636 KB Output is correct
12 Correct 52 ms 6636 KB Output is correct
13 Correct 55 ms 6636 KB Output is correct
14 Correct 109 ms 6636 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 67 ms 6636 KB Output is correct
2 Correct 54 ms 6636 KB Output is correct
3 Correct 35 ms 6636 KB Output is correct
4 Correct 45 ms 6764 KB Output is correct
5 Correct 57 ms 6764 KB Output is correct
6 Correct 63 ms 6636 KB Output is correct
7 Correct 61 ms 6636 KB Output is correct
8 Correct 59 ms 6636 KB Output is correct
9 Correct 51 ms 6636 KB Output is correct
10 Correct 59 ms 6660 KB Output is correct
11 Correct 60 ms 6636 KB Output is correct
12 Correct 52 ms 6636 KB Output is correct
13 Correct 55 ms 6636 KB Output is correct
14 Correct 109 ms 6636 KB Output is correct
15 Correct 78 ms 6636 KB Output is correct
16 Execution timed out 6050 ms 6764 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 6636 KB Output is correct
2 Correct 54 ms 6636 KB Output is correct
3 Correct 35 ms 6636 KB Output is correct
4 Correct 45 ms 6764 KB Output is correct
5 Correct 57 ms 6764 KB Output is correct
6 Correct 63 ms 6636 KB Output is correct
7 Correct 61 ms 6636 KB Output is correct
8 Correct 59 ms 6636 KB Output is correct
9 Correct 51 ms 6636 KB Output is correct
10 Correct 59 ms 6660 KB Output is correct
11 Correct 60 ms 6636 KB Output is correct
12 Correct 52 ms 6636 KB Output is correct
13 Correct 55 ms 6636 KB Output is correct
14 Correct 109 ms 6636 KB Output is correct
15 Correct 78 ms 6636 KB Output is correct
16 Execution timed out 6050 ms 6764 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 6636 KB Output is correct
2 Correct 54 ms 6636 KB Output is correct
3 Correct 35 ms 6636 KB Output is correct
4 Correct 45 ms 6764 KB Output is correct
5 Correct 57 ms 6764 KB Output is correct
6 Correct 63 ms 6636 KB Output is correct
7 Correct 61 ms 6636 KB Output is correct
8 Correct 59 ms 6636 KB Output is correct
9 Correct 51 ms 6636 KB Output is correct
10 Correct 59 ms 6660 KB Output is correct
11 Correct 60 ms 6636 KB Output is correct
12 Correct 52 ms 6636 KB Output is correct
13 Correct 55 ms 6636 KB Output is correct
14 Correct 109 ms 6636 KB Output is correct
15 Correct 78 ms 6636 KB Output is correct
16 Execution timed out 6050 ms 6764 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 6636 KB Output is correct
2 Correct 54 ms 6636 KB Output is correct
3 Correct 35 ms 6636 KB Output is correct
4 Correct 45 ms 6764 KB Output is correct
5 Correct 57 ms 6764 KB Output is correct
6 Correct 63 ms 6636 KB Output is correct
7 Correct 61 ms 6636 KB Output is correct
8 Correct 59 ms 6636 KB Output is correct
9 Correct 51 ms 6636 KB Output is correct
10 Correct 59 ms 6660 KB Output is correct
11 Correct 60 ms 6636 KB Output is correct
12 Correct 52 ms 6636 KB Output is correct
13 Correct 55 ms 6636 KB Output is correct
14 Correct 109 ms 6636 KB Output is correct
15 Correct 78 ms 6636 KB Output is correct
16 Execution timed out 6050 ms 6764 KB Time limit exceeded
17 Halted 0 ms 0 KB -