Submission #24839

#	Time	Username	Problem	Language	Result	Execution time	Memory
24839		Ushio	Arranging Tickets (JOI17_arranging_tickets)	C++14	100 / 100	1002 ms	8828 KiB

arranging_tickets

#include <bits/stdc++.h>
#define SZ(x) ((int) (x).size())
using namespace std;

typedef long long i64;

struct Segment {
    int left, right, c;
    Segment() = default;
    Segment(int _x, int _y, int _c):
        left(_x), right(_y), c(_c) {}
    bool operator<(const Segment& o) const {
        return left < o.left || (left == o.left && right < o.right);
    }
};

struct byRight {
    bool operator()(const Segment& a, const Segment& b) const {
        return a.right < b.right;
    }
};

bool works(int n,
           const vector<Segment>& a,
           const vector<int64_t>& cnt,
           int pmax,
           int64_t rem,
           int64_t take) {
    if (take > rem) {
        return false;
    }
    priority_queue<Segment, vector<Segment>, byRight> h;
    int64_t taken = 0;
    vector<int64_t> add(n, 0);
    for (int i = 0, j = 0; i <= pmax; ++i) {
        while (j < SZ(a) && a[j].left <= i) {
            h.push(a[j++]);
        }
        int64_t ctake = (cnt[i] - rem + take + 1) / 2 - taken;
        ctake = max(ctake, (int64_t) 0);
        int64_t takeNow = ctake;
        while (ctake > 0) {
            if (h.empty()) {
                return false;
            }
            Segment s = h.top();
            h.pop();
            if (s.c > ctake) {
                add[0] += ctake;
                add[s.left] -= 2 * ctake;
                add[s.right] += 2 * ctake;
                s.c -= ctake;
                ctake = 0;
                h.push(s);
            } else {
                add[0] += s.c;
                add[s.left] -= 2 * s.c;
                add[s.right] += 2 * s.c;
                ctake -= s.c;
            }
        }
        taken += takeNow;
    }
    for (int i = 1; i < n; ++i) {
        add[i] += add[i - 1];
    }
    for (int i = pmax; i < n; ++i) {
        add[i] += cnt[i];
        if (add[i] > rem) {
            return false;
        }
    }
    return true;
}

bool works(int n,
           const vector<Segment>& a,
           const vector<int64_t>& cnt,
           int pmax,
           int64_t rem) {
    if (cnt[pmax] <= rem) {
        return true;
    }
    if (works(n, a, cnt, pmax, rem, cnt[pmax] - rem)) {
        return true;
    }
    if (works(n, a, cnt, pmax, rem, cnt[pmax] - rem + 1)) {
        return true;
    }
    return false;
}

int main() {
    #ifdef LOCAL_RUN
    freopen("task.in", "r", stdin);
    freopen("task.out", "w", stdout);
    //freopen("task.err", "w", stderr);
    #endif // ONLINE_JUDGE
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, m;
    cin >> n >> m;

    vector<Segment> a(m);
    for (int i = 0; i < m; ++i) {
        cin >> a[i].left >> a[i].right >> a[i].c;
        if (a[i].right < a[i].left) {
            swap(a[i].left, a[i].right);
        }
        a[i].left--; a[i].right--;
    }
    sort(a.begin(), a.end());
    vector<int64_t> cnt(n, 0);
    for (const Segment& o: a) {
        cnt[o.left] += o.c;
        cnt[o.right] -= o.c;
    }
    for (int i = 1; i < n; ++i) {
        cnt[i] += cnt[i - 1];
    }
    int pmax = max_element(cnt.begin(), cnt.end()) - cnt.begin();
    // for (int x: cnt) cerr << x << ' '; cerr << endl;
    m = 0;
    // cerr << pmax << endl;
    for (int i = 0; i < SZ(a); ++i) {
        if (a[i].left <= pmax && pmax <= a[i].right) {
            // cerr << a[i].left << ' ' << a[i].right << endl;
            a[m++] = a[i];
        }
    }
    a.resize(m);

    // cerr << works(n, a, cnt, pmax, 9) << endl;
    // return 0;

    int64_t ans = -1;
    for (int64_t step = 1LL << 45; step > 0; step /= 2) {
    // for (int64_t step = 1; step > 0; step = 0) {
        if (!works(n, a, cnt, pmax, ans + step)) {
            ans += step;
        }
    }
    ++ans;

    cout << ans << '\n';
}

• Subtask 1: 10 / 10
• Subtask 2: 35 / 35
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 15 / 15