Submission #1261772

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261772		inkvizytor	Arranging Tickets (JOI17_arranging_tickets)	C++20	85 / 100	143 ms	16468 KiB

arranging_tickets

#include <bits/stdc++.h>
using namespace std;

#define ll long long

bool czy(ll x, ll k, vector<vector<pair<ll, ll>>> &w, vector<ll> &sum, ll mx, ll poz, ll n, ll m) {
    vector<ll> wzor (n+1, 0);
    for (ll i = 1; i <= n; i++) {
        wzor[i] = sum[i]-x+(k-sum[i]+x+1)/2;
    }
    priority_queue<pair<ll, ll>> pq;
    int s = 0;
    vector<ll> z (n+2, 0);
    for (int i = 1; i <= poz; i++) {
        for (auto q : w[i]) {
            pq.push(q);
        }
        for (int j = -s; j < wzor[i]; j++) {
            if (pq.empty()) {
                return 0;
            }
            z[pq.top().first+1]+=2;
            pq.pop();
            s--;
        }
    }
    for (int i = poz+1; i <= n; i++) {
        s += z[i];
        if (s+sum[i] > x) {
            return 0;
        }
    }
    return 1;
}

int main() {
	ios::sync_with_stdio(0); 
    cin.tie(0);
    ll n, m;
	cin >> n >> m;
    vector<pair<pair<ll, ll>, ll>> k (m);
    vector<ll> sum (n+2);
    for (ll i = 0; i < m; i++) {
        cin >> k[i].first.first >> k[i].first.second >> k[i].second;
        if (k[i].first.first > k[i].first.second) {
            swap(k[i].first.first, k[i].first.second);
        }
        k[i].first.second--;
        sum[k[i].first.first]++;
        sum[k[i].first.second+1]--;
    }
    ll mx = 0, poz = 0;
    for (ll i = 1; i <= n; i++) {
        sum[i] += sum[i-1];
        if (sum[i] > mx) {
            mx = sum[i];
            poz = i;
        }
    }
    vector<vector<pair<ll, ll>>> w (n+1);
    for (int i = 0; i < m; i++) { 
        if (k[i].first.second >= poz && k[i].first.first <= poz) {
            w[k[i].first.first].push_back({k[i].first.second, i});
        }
    }
    ll b = 0, e = mx;
    while (b < e) {
        ll s = (b + e) / 2;
        if (czy(s, mx - s, w, sum, mx, poz, n, m) || czy(s, mx - s + 1, w, sum, mx, poz, n, m)) e = s;
        else b = s + 1;
    }
    cout << b << '\n';
}

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