제출 #1161970

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1161970		jerzyk	Arranging Tickets (JOI17_arranging_tickets)	C++20	65 / 100	46 ms	4680 KiB

arranging_tickets

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
using namespace __gnu_pbds;
using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000'000'000'000'000'000LL;
const int II = 2'000'000'000;
const ll M = 1000'000'007LL;
const int N = 1<<17;
pair<int, int> tab[N];
ll il[N];
ll sum[N];
ll nw[N];
int pos = 0;

ll lft[N];


bool Try(int n, int m, ll ilo, ll x)
{
    priority_queue<pair<int, int>> q;

    for(int i = 1; i <= n; ++i) nw[i] = 0LL;
    ll s = 0LL;
    int j = 0;
    for(int i = 1; i <= pos; ++i)
    {
        while(j < m && tab[j + 1].st <= i)
        {
            ++j;
            if(tab[j].nd >= pos + 1)
                q.push(make_pair(tab[j].nd, j));
            lft[j] = il[j];
        }
        ll cr = (sum[i] - s - x) + ((ilo - s + 1LL - (sum[i] - s - x)) / 2LL);
        //cout << i << " " << sum[i] << " " << s << " " << cr << "\n";
        cr = max(cr, 0LL);
        if(s + cr > ilo) return 0;
        while((int)q.size() > 0 && cr > 0LL)
        {
            int l = q.top().nd;
            ll d = min(cr, lft[l]);
            //cout << "Q: " << l << " " << d << " " << cr << " " << tab[l].st << " " << tab[l].nd << "\n";
            lft[l] -= d;
            cr -= d;
            nw[1] += d; nw[tab[l].st] -= 2LL * d;
            nw[tab[l].nd] += 2LL * d; nw[n + 1] -= d;
            s += d;
            if(lft[l] == 0LL)
                q.pop();
        }
        if(cr > 0LL) return 0;
    }
    for(int i = 1; i <= n; ++i)
        nw[i] += nw[i - 1];
    for(int i = 1; i <= n; ++i)
    {
        nw[i] += sum[i];
        //cout << nw[i] << "\n";
        if(nw[i] > x) return 0;
    }
    return 1;
}

bool Check(int n, int m, ll x)
{
    if(x >= sum[pos]) return 1;
    if(Try(n, m, sum[pos] - x, x))
        return 1;
    if(Try(n, m, sum[pos] - x + 1LL, x))
        return 1;
    return 0;
}

ll BS(int n, int m, ll lim)
{
    ll p = 1LL, k = lim, s;
    while(p < k)
    {
        s = (p + k) / 2;
        //cout << p << " " << k << " " << s << "\n";
        if(Check(n, m, s))
            k = s;
        else
            p = s + 1;
    }
    return p;
}

void Solve()
{
    int n, m; ll lim = 0LL;
    cin >> n >> m;
    for(int i = 1; i <= m; ++i)
    {
        cin >> tab[i].st >> tab[i].nd >> il[i];
        if(tab[i].st > tab[i].nd)
            swap(tab[i].st, tab[i].nd);
        sum[tab[i].st] += il[i];
        sum[tab[i].nd] -= il[i];
        lim += il[i];
    }
    sort(tab + 1, tab + 1 + m);
    ll ma = 0LL;
    for(int i = 1; i <= n; ++i)
    {
        sum[i] += sum[i - 1];
        if(sum[i] > ma)
        {
            pos = i; ma = sum[i];
        }
    }
    //cout << Try(n, m, 1, 2LL) << "\n";
    ll ans = 0LL; 
    ans = BS(n, m, lim);
    cout << ans << "\n";
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    //int t; cin >> t;
    //while(t--)
        Solve();

    return 0;
}

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