oj.uz

Submission #366999

# Submission time Handle Problem Language Result Execution time Memory
366999 2021-02-16T02:30:48 Z fishy15 Arranging Tickets (JOI17_arranging_tickets) C++14
0 / 100
 15 ms 6636 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++) {
        if (check(m, i, min_check) || check(m, i, max_check)) {
            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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 6636 KB Output is correct
2 Correct 10 ms 6636 KB Output is correct
3 Correct 10 ms 6636 KB Output is correct
4 Correct 10 ms 6636 KB Output is correct
5 Correct 9 ms 6636 KB Output is correct
6 Correct 11 ms 6636 KB Output is correct
7 Correct 10 ms 6636 KB Output is correct
8 Correct 11 ms 6636 KB Output is correct
9 Correct 9 ms 6636 KB Output is correct
10 Correct 12 ms 6636 KB Output is correct
11 Correct 10 ms 6636 KB Output is correct
12 Correct 9 ms 6636 KB Output is correct
13 Correct 11 ms 6636 KB Output is correct
14 Correct 15 ms 6636 KB Output is correct
15 Incorrect 10 ms 6636 KB Output isn't correct

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 6636 KB Output is correct
2 Correct 10 ms 6636 KB Output is correct
3 Correct 10 ms 6636 KB Output is correct
4 Correct 10 ms 6636 KB Output is correct
5 Correct 9 ms 6636 KB Output is correct
6 Correct 11 ms 6636 KB Output is correct
7 Correct 10 ms 6636 KB Output is correct
8 Correct 11 ms 6636 KB Output is correct
9 Correct 9 ms 6636 KB Output is correct
10 Correct 12 ms 6636 KB Output is correct
11 Correct 10 ms 6636 KB Output is correct
12 Correct 9 ms 6636 KB Output is correct
13 Correct 11 ms 6636 KB Output is correct
14 Correct 15 ms 6636 KB Output is correct
15 Incorrect 10 ms 6636 KB Output isn't correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 6636 KB Output is correct
2 Correct 10 ms 6636 KB Output is correct
3 Correct 10 ms 6636 KB Output is correct
4 Correct 10 ms 6636 KB Output is correct
5 Correct 9 ms 6636 KB Output is correct
6 Correct 11 ms 6636 KB Output is correct
7 Correct 10 ms 6636 KB Output is correct
8 Correct 11 ms 6636 KB Output is correct
9 Correct 9 ms 6636 KB Output is correct
10 Correct 12 ms 6636 KB Output is correct
11 Correct 10 ms 6636 KB Output is correct
12 Correct 9 ms 6636 KB Output is correct
13 Correct 11 ms 6636 KB Output is correct
14 Correct 15 ms 6636 KB Output is correct
15 Incorrect 10 ms 6636 KB Output isn't correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 6636 KB Output is correct
2 Correct 10 ms 6636 KB Output is correct
3 Correct 10 ms 6636 KB Output is correct
4 Correct 10 ms 6636 KB Output is correct
5 Correct 9 ms 6636 KB Output is correct
6 Correct 11 ms 6636 KB Output is correct
7 Correct 10 ms 6636 KB Output is correct
8 Correct 11 ms 6636 KB Output is correct
9 Correct 9 ms 6636 KB Output is correct
10 Correct 12 ms 6636 KB Output is correct
11 Correct 10 ms 6636 KB Output is correct
12 Correct 9 ms 6636 KB Output is correct
13 Correct 11 ms 6636 KB Output is correct
14 Correct 15 ms 6636 KB Output is correct
15 Incorrect 10 ms 6636 KB Output isn't correct

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 6636 KB Output is correct
2 Correct 10 ms 6636 KB Output is correct
3 Correct 10 ms 6636 KB Output is correct
4 Correct 10 ms 6636 KB Output is correct
5 Correct 9 ms 6636 KB Output is correct
6 Correct 11 ms 6636 KB Output is correct
7 Correct 10 ms 6636 KB Output is correct
8 Correct 11 ms 6636 KB Output is correct
9 Correct 9 ms 6636 KB Output is correct
10 Correct 12 ms 6636 KB Output is correct
11 Correct 10 ms 6636 KB Output is correct
12 Correct 9 ms 6636 KB Output is correct
13 Correct 11 ms 6636 KB Output is correct
14 Correct 15 ms 6636 KB Output is correct
15 Incorrect 10 ms 6636 KB Output isn't correct