Submission #535517

#	Time	Username	Problem	Language	Result	Execution time	Memory
535517		extraterrestrial	Arranging Tickets (JOI17_arranging_tickets)	C++17	45 / 100	6040 ms	37480 KiB

arranging_tickets

#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()

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++) {
            vector<multiset<pair<int, int>>> segments(n);
            vector<int> cnt(n);
            for (int left_border = 0; left_border < n; left_border++) {
                for (auto right_border : have[left_border]) {
                    cnt[left_border]++;
                    cnt[right_border + 1]--;
                    segments[left_border].insert({right_border, left_border});
                }
            }
            for (int i = 1; i < n; i++) {
                cnt[i] += cnt[i - 1];
            }

            bool ok = true;
            int already_flipped = 0;
            for (int i = 0; i + 1 < n; i++) {
                int need_flip = max(0, (cnt[i] + (cnt_flip - already_flipped) - mid + 1) / 2);
                /*if (mid == 1 && cnt_flip == 1) {
                    cerr << i << ' ' << need_flip << '\n';
                    for (int j = 0; j < n; j++) {
                        cerr << cnt[j] << ' ';
                    }
                    cerr << '\n';
                }*/
                if (already_flipped + need_flip > cnt_flip) {
                    ok = false;
                    break;
                }
                if (SZ(segments[i]) < need_flip) {
                    ok = false;
                    break;
                }
                for (int j = 0; j < need_flip; j++) {
                    auto [right_border, left_border] = *segments[i].rbegin();
                    segments[i].erase(--segments[i].end());
                    /*if (mid == 1 && cnt_flip == 1) {
                        cerr << "REVERSE " << left_border << ' ' << right_border << '\n';
                    }*/
                    for (int k = 0; k < n; k++) {
                        if (k >= left_border && k <= right_border) {
                            cnt[k]--;
                        } else {
                            cnt[k]++;
                        }
                    }
                }
                for (auto [right_border, left_border] : segments[i]) {
                    if (right_border >= i + 1) {
                        segments[i + 1].insert({right_border, left_border});
                    }
                }
                already_flipped += need_flip;
            }
            for (int i = 0; i < n; i++) {
                if (cnt[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