Submission #1261774

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261774		inkvizytor	Arranging Tickets (JOI17_arranging_tickets)	C++20	100 / 100	706 ms	17488 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;
    ll s = 0;
    vector<ll> z (n+2, 0);
    for (ll i = 1; i <= poz; i++) {
        for (auto q : w[i]) {
            pq.push(q);
        }
        ll su = -s;
        while (!pq.empty() && su < wzor[i]) {
            auto q = pq.top();
            pq.pop();
            ll f = min(q.second, wzor[i]-su);
            su += f;
            s -= f;
            z[q.first+1] += 2*f;
            if (f < q.second) {
                pq.push({q.first, q.second-f});
            } 
        }
        if (su < wzor[i]) return 0;
    }
    for (ll 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]+=k[i].second;
        sum[k[i].first.second+1]-=k[i].second;
    }
    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, k[i].second});
        }
    }
    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: 15 / 15