제출 #1260535

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1260535		M_W_13	Arranging Tickets (JOI17_arranging_tickets)	C++20	0 / 100	2 ms	4928 KiB

arranging_tickets

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define st first
#define nd second
#define pb push_back

struct tr {
    int l, r;
    ll c;
};

const int MAXN = 2e5 + 7;
int n, m;
tr T[MAXN];
ll ile[MAXN];
ll dod[MAXN];
ll dod2[MAXN];
ll policz[MAXN];
ll policz2[MAXN];
vector<pair<int, int>> jakie[MAXN];

bool check(ll f, ll k, int kt) {
    // cout << "k = " << k << '\n';
    // cout << "f = " << f << '\n';
    rep(i, m + 1) {
        ile[i] = T[i].c;
    }
    rep(i, n + 2) {
        jakie[i].clear();
        dod2[i] = dod[i];
        policz2[i] = 0ll;
    }
    priority_queue<pair<int, int>> pq;
    rep(i, m) {
        if (T[i].l <= kt && T[i].r >= kt) {
            jakie[T[i].l].pb({T[i].r, i});
        }
    }
    ll pol = 0;
    for (int i = 0; i <= kt; i++) {
        ll liczba = max(0ll, (policz[i] - pol - k + f)/2);
        for (auto par: jakie[i]) {
            pq.push(par);
        }
        // cout << "liczba = " << liczba << '\n';
        while (liczba > 0) {
            if (pq.empty()) {
                return false;
            }
            pair<int, int> p = pq.top();
            pq.pop();
            int l = T[p.nd].l;
            int r = T[p.nd].r;
            ll spp = 0;
            if (ile[p.nd] <= liczba) {
                liczba -= ile[p.nd];
                spp = ile[p.nd];
                ile[p.nd] = 0;
            }
            else {
                ile[p.nd] -= liczba;
                spp = liczba;
                liczba = 0ll;
                pq.push(p);
            }
            f -= spp;
            dod2[l] -= spp;
            dod2[r + 1] += spp;
            dod2[0] += spp;
            dod2[l] -= spp;
            dod2[r + 1] += spp;
        }
    }
    ll s = 0;
    rep(i, n + 1) {
        s += dod2[i];
        policz2[i] = s;
        if (s > k) {
            return false;
        }
    }
    return true;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    rep(i, m) {
        cin >> T[i].l >> T[i].r >> T[i].c;
        if (T[i].l > T[i].r) {
            swap(T[i].l, T[i].r);
        }
        dod[T[i].l] += T[i].c;
        dod[T[i].r] -= T[i].c;
        T[i].r--;
    }
    policz[0] = 0;
    for (int i = 1; i < n; i++) {
        policz[i] = policz[i - 1] + dod[i];
    }
    rep(i, n + 1) {
        dod[i] = 0;
    }
    ll x = 0;
    int kt = 0;
    rep(i, n) {
        if (policz[i] >= x) {
            x = policz[i];
            kt = i;
        }
    }
    ll poc = 1;
    ll kon = x;
    ll odp = x;
    // cout << "x = " << x << '\n';
    while (poc < kon) {
        ll sr = (poc + kon)/2;
        if (check(x - sr, sr, kt) || check(x - sr + 1, sr, kt)) {
            odp = sr;
            kon = sr;
        }
        else {
            poc = sr + 1;
        }
    }
    cout << odp << '\n';
    return 0;
}

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