Submission #1260553

#	Time	Username	Problem	Language	Result	Execution time	Memory
1260553		patgra	Arranging Tickets (JOI17_arranging_tickets)	C++20	100 / 100	1114 ms	19064 KiB

arranging_tickets

#include <bits/stdc++.h>

#define rep(a,b,c) for(auto a = (b); a != (c); a++)
#define repD(a,b,c) for(auto a = (b); a != (c); a--)
#define repIn(a, b) for(auto& a : (b))
#define repIn2(a, b, c) for(auto& [a, b] : (c))

constexpr bool dbg = 1;
#define DEBUG if constexpr(dbg)
#define DC DEBUG std::cerr
#define eol std::endl

#define ll long long
#define pb push_back

using namespace std;

#define int ll

int32_t main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<pair<pair<int, int>, int>> v;
    map<pair<int, int>, int> mp;
    rep(i, 0, m) {
        int a, b, c;
        cin >> a >> b  >> c;
        a--; b--;
        if(a > b) swap(a, b);
        b--;
        mp[{a, b}] += c;
    }
    repIn(i, mp) v.pb(i);
    m = v.size();

    pair<int, int> mx = {-1, -1};
    vector<int> over;
    vector<pair<int, int>> begs, ends;
    repIn2(ab, c, v) begs.pb({ab.first, c}), ends.pb({ab.second, c});
    ranges::sort(begs), ranges::sort(ends);
    int bi = 0, ei = 0;
    int cur = 0;
    rep(i, 0, n) {
        while(bi < m && begs[bi].first <= i) cur += begs[bi++].second;
        while(ei < m && ends[ei].first < i) cur -= ends[ei++].second;
        mx = max(mx, {cur, i});
        over.pb(cur);
    }

    int l = 0, r = mx.first;
    while(r - l > 1) {
        int md = (l + r) / 2;
        bool works = false;
        rep(out, mx.first - md, mx.first - md + 2) {
            // over + out - 2x <= md
            // 2x >= over + out - md
            // x >= (over + out - md) / 2
            priority_queue<pair<int, int>> q;
            int vi = 0, turned = 0;
            vector<pair<int, int>> whereTo;
            bool g = true;
            rep(i, 0, mx.second + 1) {
                while(vi < m && v[vi].first.first <= i) {
                    if(v[vi].first.second >= mx.second) q.push({v[vi].first.second, v[vi].second});
                    vi++;
                }
                int need = (over[i] + out - md + 1) / 2;
                while(q.size() && turned < need) {
                    auto [end, val] = q.top();
                    q.pop();
                    if(val <= need - turned) {
                        turned += val;
                        whereTo.pb({end, val});
                    }
                    else {
                        whereTo.pb({end, need - turned});
                        val -= need - turned;
                        turned = need;
                        q.push({end, val});
                    }
                }
                if(turned < need) { g = false; break; }
            }
            if(!g) continue;
            ranges::sort(whereTo);
            int wti = 0;
            rep(i, mx.second + 1, n) {
                while(wti < (int)whereTo.size() && whereTo[wti].first < i) turned -= whereTo[wti++].second;
                int need = (over[i] + out - md + 1) / 2;
                if(turned < need) { g = false; break; }
            }
            if(!g) continue;
            works = true;
            // TODO maybe check n?
            break;
        }
        (works ? r : l) = md;
    }
    cout << r << eol;
}

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