Submission #1158948

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158948		jerzyk	Arranging Tickets (JOI17_arranging_tickets)	C++20	0 / 100	2 ms	2376 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 lft[N];
ll drz[2 * N], laz[2 * N];

void Add(int v, int p, int k, int pz, int kz, ll x)
{
    if(p > kz || k < pz) return;
    if(p >= pz && k <= kz)
    {
        laz[v] += x; drz[v] += x;
        return;
    }
    Add(v * 2, p, (p + k) / 2, pz, kz, x);
    Add(v * 2 + 1, (p + k) / 2 + 1, k, pz, kz, x);
}

inline void A(int a, int b, ll x)
{
    if(a <= b)
        Add(1, 0, N - 1, a, b, x);
}

ll Query(int v, int p, int k, int pz, int kz)
{
    if(p > kz || k < pz) return 0LL;
    if(p >= pz && k <= kz)
        return drz[v];
    ll a = Query(v * 2, p, (p + k) / 2, pz, kz);
    a = max(a, Query(v * 2 + 1, (p + k) / 2 + 1, k, pz, kz));
    return a + laz[v];
}

inline ll Q(int a, int b)
{
    if(a > b) return 0LL;
    return Query(1, 0, N - 1, a, b);
}

ll Val(int v)
{
    v += N;
    ll ans = drz[v];
    v /= 2;
    while(v > 0)
    {
        ans += laz[v];
        v /= 2;
    }
    return ans;
}

bool Check(int n, int m, ll x)
{
    for(int i = N + 1; i <= N + n; ++i)
        {drz[i] = 0; laz[i] = 0;}
    for(int i = 1; i <= m; ++i)
    {
        drz[tab[i].st + N] += il[i];
        drz[tab[i].nd + N] -= il[i];
    }
    for(int i = N + 1; i <= N + n; ++i)
        drz[i] += drz[i - 1];
    for(int i = N - 1; i >= 1; --i)
    {
        drz[i] = max(drz[i * 2], drz[i * 2 + 1]);
        laz[i] = 0;
    }
    priority_queue<pair<pair<int, int>, int>> q;
    int j = 0;
    for(int i = 1; i <= n; ++i)
    {
        while(j < m && tab[j + 1].st >= i)
        {
            ++j;
            q.push(make_pair(make_pair(tab[j].nd, -tab[j].st), j));
            lft[j] = il[j];
        }
        ll cur = Val(i);
        //cout << "POS: " << i << " " << cur << "\n";
        while((int)q.size() > 0 && cur > x)
        {
            if(q.top().st.st <= i) {q.pop(); continue;}

            int b = q.top().st.st, a = -q.top().st.nd, l = q.top().nd;
            lft[l] = min(lft[l], x - max(Q(1, a - 1), Q(b, n)));
            //cout << "Qa" << " " << Q(1, a - 1) << "\n";
            //cout << "C: " << a << " " << b << " " << l << " " << lft[l] << " " << cur << "\n";
            ll d = max(0LL, min(cur - x, lft[l]));
            cur -= d;
            lft[l] -= d;
            A(a, b - 1, -d);
            A(1, a - 1, d);
            A(b, n, d);

            if(lft[l] <= 0LL)
                q.pop();
        }
        if(cur > x) return 0;
    }
    return 1;
}

ll BS(int n, int m, ll lim)
{
    ll p = 1LL, k = lim, s;
    while(p < k)
    {
        s = (p + k) / 2;
        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);
        lim += il[i];
    }
    //cout << Check(n, m, 1) << "\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: 0 / 10
• Subtask 2: 0 / 35
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 15