Submission #535528

#	Time	Username	Problem	Language	Result	Execution time	Memory
535528		extraterrestrial	Arranging Tickets (JOI17_arranging_tickets)	C++17	45 / 100	6052 ms	508 KiB

arranging_tickets

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;
#define all(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()

struct fenwick {
    int n;
    vector<int> t;
    explicit fenwick(int _n) : n(_n) {
        t.resize(n + 1, 0);
    }
    void update(int v, int delta) {
        for (; v <= n; v += v & (-v)) {
            t[v] += delta;
        }
    }
    void add_on_segment(int l, int r, int delta) {
        l++, r++;
        update(l, delta);
        update(r + 1, -delta);
    }
    int get_value(int v) {
        v++;
        int result = 0;
        for (; v > 0; v -= v & (-v)) {
            result += t[v];
        }
        return result;
    }
};

signed main() {
#ifdef PC
    freopen("input.txt", "r", stdin);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<vector<int>> have(n);
    for (int i = 0; i < m; i++) {
        int from, to, cnt;
        cin >> from >> to >> cnt;
        from--, to--;
        if (from > to) {
            swap(from, to);
        }
        if (from < to) {
            have[from].push_back(to - 1);
        }
    }
    int l = -1, r = m;
    while (r - l > 1) {
        int mid = (l + r) / 2;
        bool can = false;
        for (int cnt_flip = 0; cnt_flip <= mid; cnt_flip++) {
            multiset<pair<int, int>> segments;
            fenwick cnt(n);
            for (int left_border = 0; left_border < n; left_border++) {
                for (auto right_border : have[left_border]) {
                    cnt.add_on_segment(left_border, right_border, 1);
                }
            }

            bool ok = true;
            int already_flipped = 0;
            for (int i = 0; i + 1 < n; i++) {
                int need_flip = max(0, (cnt.get_value(i) + (cnt_flip - already_flipped) - mid + 1) / 2);
                if (already_flipped + need_flip > cnt_flip) {
                    ok = false;
                    break;
                }
                for (auto right_border : have[i]) {
                    segments.insert({right_border, i});
                }
                if (SZ(segments) < need_flip) {
                    ok = false;
                    break;
                }
                for (int j = 0; j < need_flip; j++) {
                    auto [right_border, left_border] = *segments.rbegin();
                    segments.erase(--segments.end());

                    cnt.update(1, 1);
                    cnt.update(left_border + 1, -2);
                    cnt.update(right_border + 2, 2);
                    //cnt.add_on_segment(left_border, right_border, -1);
                    //cnt.add_on_segment(0, left_border - 1, 1);
                    //cnt.add_on_segment(right_border + 1, n - 1, 1);
                }
                while (!segments.empty() && segments.begin()->first < i + 1) {
                    segments.erase(segments.begin());
                }
                already_flipped += need_flip;
            }
            for (int i = 0; i < n; i++) {
                if (cnt.get_value(i) > mid) {
                    ok = false;
                    break;
                }
            }
            if (ok) {
                can = true;
                break;
            }
        }
        if (can) {
            r = mid;
        } else {
            l = mid;
        }
    }
    cout << r << '\n';
}

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