Submission #1261584

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261584		Szymon_Pilipczuk	Arranging Tickets (JOI17_arranging_tickets)	C++20	100 / 100	1265 ms	17908 KiB

arranging_tickets

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(),a.end()
#define rep(a,b) for(int a = 0;a<b;a++)
#define int ll
const int inf = 1e9;
const ll infl = 1e18;
int n,m;
vector<array<int,3>> frag;
vector<array<int,3>> ev;
vector<array<int,3>> bett;
ll val[200000];
ll need[200000];
pair<ll,int> mx = {-1,-1};
bool solve(ll k)
{

    ll dn = val[mx.nd]-k;
    //cerr<<dn<<" "<<k<<"\n";
    rep(tt,2)
    {
        rep(i,n-1)
        {
            need[i] = (val[i] - k + dn + 1)/2;
        //    cerr<<need[i]<<" ";
        }
        //cerr<<"\n";
        priority_queue<pair<int,ll>> pq;
        ll cv = 0;
        priority_queue<pair<int,ll>,vector<pair<int,ll>>,greater<pair<int,ll>>> ev;
        int j = 0;
        ll am = 0;
        bool exit = false;
        rep(i,n-1)
        {
            //if(!ev.empty())cerr<<i<<" "<<ev.top().st<<" "<<ev.top().nd<<" "<<"\n";
            while(j != bett.size() && bett[j][0]  == i)
            {
                pq.push({bett[j][1],bett[j][2]});
                j++;
            }
            while(!ev.empty() && ev.top().st == i)
            {
                cv -= ev.top().nd;
                ev.pop();
            }
            while(cv < need[i])
            {
                if(!pq.empty())
                {
                    if(pq.top().st < i)
                    {
                        pq.pop();
                        continue;
                    }
                    if(cv + pq.top().nd <= need[i])
                    {
                        ev.push({pq.top().st+1,pq.top().nd});
                        cv += pq.top().nd;
                        am += pq.top().nd;
                        //cerr<<am<<" "<<cv<<" "<<pq.top().st<<" "<<pq.top().nd<<"\n";
                        pq.pop();
                    }
                    else
                    {
                        //cerr<<pq.top().st<<" "<<pq.top().nd<<"\n";
                        pair<int,int> cc = pq.top();
                        pq.pop();
                        ev.push({cc.st+1,need[i] - cv});
                        pq.push({cc.st,cc.nd - (need[i] - cv)});
                        am += need[i] - cv;
                        //cerr<<need[i]-cv<<"\n";
                        cv = need[i];
                        //cerr<<am<<" "<<cv<<" "<<pq.top().st<<" "<<pq.top().nd<<"\n";
                    }
                }
                else
                {
                    exit = true;
                }
                if(am > dn || am > k)
                {
                    exit = true;
                }
                if(exit) break;
            }
            if(exit) break;
        }
        if(!exit)
        {
            return 1;
        }

        dn++;
    }
    return 0;
}
int32_t main()
{
    cin>>n>>m;
    frag.resize(m);
    rep(i,m)
    {
        int a,b,c;
        cin>>a>>b>>c;
        a--;b--;
        if(a > b)
        {
            swap(a,b);
        }
        b--;
        frag[i] = {a,b,c};
    }
    sort(all(frag));
    rep(i,m)
    {
        ev.pb({frag[i][0],1,frag[i][2]});
        ev.pb({frag[i][1] + 1,-1,frag[i][2]});
    }
    sort(all(ev));
    int j = 0;
    ll cu = 0;
    rep(i,n-1)
    {
        while(j != m*2 && ev[j][0] == i)
        {
            cu += ev[j][1] * ev[j][2];
            j++;
        }
        val[i] = cu;
        if(cu > mx.st)
        {
            mx.st = cu;
            mx.nd = i;
        }
    }
    rep(i,m)
    {
        if(frag[i][0] <= mx.nd && mx.nd <= frag[i][1])
        {
            bett.pb(frag[i]);
            //cerr<<bett.back()[0]<<" "<<bett.back()[1]<<" "<<bett.back()[2]<<"\n";
        }
    }
    //cerr<<mx.st<<" "<<mx.nd<<"\n";
    //cerr<<solve(5)<<"\n";
    ll l = 0;
    ll r = infl;
    while(l + 1 < r)
    {
        ll mid = (l+r)/2;
        if(solve(mid))
        {
            r = mid;
        }
        else
        {
            l = mid;
        }
    }
    cout<<r<<"\n";
}

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