제출 #1261244

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1261244		SzymonKrzywda	Arranging Tickets (JOI17_arranging_tickets)	C++20	큐에 대기중	0 ms	0 KiB

arranging_tickets

#include <iostream>
#include <queue>

using namespace std;
using ll = unsigned long long;

ll maxi = 0, maxi_pos = 0;

const ll MAXN = 2e5 + 4;
vector<pair<ll, ll>> konce[MAXN];
ll sumy[MAXN];

ll n, m, a, b, c;

bool check(ll maxi_val, ll k) {
    priority_queue<pair<ll, ll>> kolejka;
    ll ile_usunalem = 0;

    vector<ll> sumy2(n + 2, 0);

    for (ll i = 1; i <= maxi_pos; i++) {
        for (auto k : konce[i]) kolejka.push(k);
        ll wzorek = sumy[i] - maxi_val + (k - sumy[i] + maxi_val + 1) / 2;
        //cout << "DUPA: " << wzorek << '\n';
        //cout << maxi_val << ' ' << k << ' ' << i << ' ' << wzorek << '\n';
        while (wzorek > ile_usunalem && kolejka.size()) {
            ll koniec = kolejka.top().first;
            ll ile = kolejka.top().second;
            ll ile_biore = min(wzorek - ile_usunalem, ile);
            kolejka.pop();
            ile_usunalem += ile_biore;
            sumy2[maxi_pos] -= ile_biore;
            sumy2[koniec + 1] += 2 * ile_biore;
        }
        //cout << "DU: " << wzorek << ' ' << ile_usunalem << ' ' << maxi_pos << ' ' << konce[i].size() << '\n';

        if (wzorek > ile_usunalem) return 0;
    }

    for (ll i = maxi_pos + 1; i <= n; i++) {
        sumy2[i] += sumy2[i - 1];
        //cout << i << ' ' << sumy2[i] << ' ' << sumy[i] << '\n';
        if (sumy2[i] + sumy[i] > maxi_val) return 0;
    }  
    //cout << maxi_val << '\n';

    return 1;
}


int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;

    vector<pair<ll, ll>> prz;
    vector<ll> ile_prz(m);

    for (ll i = 0; i < m; i++) {
        cin >> a >> b >> ile_prz[i];
        if (a > b) swap(a, b); 
        b--;
        prz.push_back({a, b});
        sumy[a] += ile_prz[i];
        sumy[b + 1] -= ile_prz[i];
    }
    


    for (ll i = 1; i <= n; i++) {
        sumy[i] += sumy[i - 1];
        if (maxi < sumy[i]) maxi_pos = i;
        maxi = max(sumy[i], maxi);
    }

    for (ll i = 0; i < m; i++) {
        if (prz[i].first <= maxi_pos && prz[i].second >= maxi_pos) konce[prz[i].first].push_back({prz[i].second, ile_prz[i]});
    }

    ll left = 0, right = maxi;
    while (left < right) {
        ll mid = (left + right) / 2;
        if (check(mid, maxi - mid) || check(mid, maxi - mid + 1)) right = mid;
        else left = mid + 1;
    }
    
    cout << left;

    return 0;
}