Submission #1260400

#	Time	Username	Problem	Language	Result	Execution time	Memory
1260400		user736482	Arranging Tickets (JOI17_arranging_tickets)	C++20	100 / 100	607 ms	20144 KiB

arranging_tickets

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define MOD 1000000007
#define INF 1000000019
#define POT (1<<21)
#define INFL 4000000000000000099LL

ll n,m,a,b,c;
vector<pair<pair<ll,ll>,ll>>v,v2;
ll il[200007];
vector<pair<ll,ll>>kon[200007];
 pair<ll,ll>mx={-1,-1};
bool czy(ll x,ll k){// czy da sie x odwracajc k
    priority_queue<pair<ll,ll>>q;
    ll licz[200007];
    for(ll i=0;i<200007;i++)licz[i]=0;
    ll ak=0;
    vector<pair<ll,ll>>wz;//kon,ile
    for(ll i=0;i<=mx.ss;i++){
        ll co=il[i]-x+(k-il[i]+x+1)/2;
        for(auto j : kon[i]){
            q.push(j);
        }
        while(co>ak){
            if(q.empty())return 0;
            auto j =q.top();
            q.pop();
            if(j.ss+ak>co){
                j.ss-=(co-ak);

                wz.pb({j.ff,co-ak});
                ak=co;
                q.push(j);
            }
            else{
                wz.pb({j.ff,j.ss});
                ak+=j.ss;
            }
        }
    }
    //licz[mx.ss]+=k;
    for(auto i : wz){
       // cout<<i.ff<<" xd "<<i.ss<<"\n";
        licz[i.ff]+=i.ss;
    }
    
    for(ll i=mx.ss+1;i<n;i++){
        licz[i]+=licz[i-1];
       // cout<<licz[i]<<"  "<<il[i]<<"\n";
        if(2*licz[i]-k+il[i]>x){//cout<<"xd";
            return 0;}
    }
    return 1;
}
ll s;
int main()
{
    cin>>n>>m;
    for(ll i=0;i<m;i++){
        cin>>a>>b>>c;
        a%=n;
        b%=n;
        if(a>b)swap(a,b);
      //  cout<<a<<" "<<b<<" "<<c<<"  ";
        il[a]+=c;
        s+=c;
        il[b]-=c;
        v.pb({{a,b},c});
    }
    for(ll i=1;i<n;i++){il[i]+=il[i-1];
      //  cout<<il[i]<<" ";
    }
   
    for(ll i=0;i<n;i++){
        mx=max(mx,{il[i],i});
    }
    swap(v,v2);
    for(auto i : v2){
        if(i.ff.ff<=mx.ss && i.ff.ss>mx.ss){
            v.pb(i);
            kon[i.ff.ff].pb({i.ff.ss,i.ss});
        }
    }
   // cout<<mx.ff<<" "<<mx.ss<<"\n\n";
    for(ll i=0;i<n;i++){
       // cout<<i<<": ";
       // for(auto j : kon[i])cout<<j.ff<<" ";
       // cout<<"\n";
    }
    ll pocz=1;
    ll kon=s;
    while(pocz!=kon){
        ll mid=(pocz+kon)/2;
        //cout<<mid<<"mid "; 
        if(czy(mid,mx.ff-mid) || czy(mid,mx.ff-mid+1))kon=mid;
        else pocz=mid+1;
    }
    cout<<pocz;
}

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