Submission #208345

#	Time	Username	Problem	Language	Result	Execution time	Memory
208345		gs18115	Arranging Tickets (JOI17_arranging_tickets)	C++14	85 / 100	730 ms	16876 KiB

arranging_tickets

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18+7;
int n,m;
ll s[200010];
ll s2[200010];
vector<pl>qv[200010];
priority_queue<pl>pq;
inline bool able(int x,ll mx,vector<pair<pi,ll> >&v)
{
    if(mx>=s[x])
        return 1;
    for(int i=0;i++<n;)
        s2[i]=s[i]-s[i-1],qv[i].clear();
    for(auto&t:v)
        qv[t.fi.fi].eb(t.fi.se,t.se);
    bool f=1;
    ll c=0;
    ll rev=s[x]-mx;
    s2[0]=rev;
    while(!pq.empty())
        pq.pop();
    for(int i=0;i++<n;)
    {
        s2[i]+=s2[i-1];
        for(pl&t:qv[i])
            pq.ep(t);
        ll rn=s2[i]>mx?(s2[i]-mx+1)/2:0;
        while(rn>0&&!pq.empty())
        {
            pl t=pq.top();
            if(t.fi<i)
                break;
            pq.pop();
            c+=min(t.se,rn);
            s2[i]-=2*min(t.se,rn);
            s2[t.fi+1]+=2*min(t.se,rn);
            if(t.se<=rn)
                rn-=t.se;
            else
            {
                t.se-=rn;
                rn=0;
                pq.ep(t);
            }
        }
        if(rn>0)
        {
            f=0;
            break;
        }
    }
    if(f&&c<=rev)
        return 1;
    for(int i=0;i++<n;)
        s2[i]=s[i]-s[i-1];
    f=1;
    c=0;
    rev=s[x]-mx+1;
    s2[0]=rev;
    while(!pq.empty())
        pq.pop();
    for(int i=0;i++<n;)
    {
        s2[i]+=s2[i-1];
        for(pl&t:qv[i])
            pq.ep(t);
        ll rn=s2[i]>mx?(s2[i]-mx+1)/2:0;
        while(rn>0&&!pq.empty())
        {
            pl t=pq.top();
            if(t.fi<i)
                break;
            pq.pop();
            c+=min(t.se,rn);
            s2[i]-=2*min(t.se,rn);
            s2[t.fi+1]+=2*min(t.se,rn);
            if(t.se<=rn)
                rn-=t.se;
            else
            {
                t.se-=rn;
                rn=0;
                pq.ep(t);
            }
        }
        if(rn>0)
        {
            f=0;
            break;
        }
    }
    if(f&&c<=rev)
        return 1;
    return 0;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>m;
    vector<pair<pi,ll> >it(m);
    for(auto&t:it)
        cin>>t.fi.fi>>t.fi.se>>t.se;
    for(auto&t:it)
        if(t.fi.fi>t.fi.se)
            swap(t.fi.fi,t.fi.se);
    for(auto&t:it)
        s[t.fi.fi]+=t.se,s[t.fi.se--]-=t.se;
    s[0]=0;
    for(int i=0;i++<n;)
        s[i]+=s[i-1];
    int m=-1;
    int mi=-1,mj=-1;
    for(int i=0;i++<n;)
    {
        if(s[i]>m)
            m=s[i],mi=i;
        if(s[i]==m)
            mj=i;
    }
    ll l=0,r=INF;
    vector<pair<pi,ll> >qv;
    for(auto&t:it)
        if(t.fi.fi<=mi&&t.fi.se>=mi)
            qv.eb(t);
    while(l<r)
    {
        ll mid=(l+r)/2;
        if(able(mi,mid,qv))
            r=mid;
        else
            l=mid+1;
    }
    ll l0=l;
    l=0,r=INF;
    qv.clear();
    for(auto&t:it)
        if(t.fi.fi<=mj&&t.fi.se>=mj)
            qv.eb(t);
    while(l<r)
    {
        ll mid=(l+r)/2;
        if(able(mj,mid,qv))
            r=mid;
        else
            l=mid+1;
    }
    cout<<min(l,l0)<<endl;
    return 0;
}

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