제출 #1260525

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1260525		Zbyszek99	Arranging Tickets (JOI17_arranging_tickets)	C++20	100 / 100	677 ms	17900 KiB

arranging_tickets

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;

struct seg
{
    int l,r;
    ll c;
};

int n,m;
vector<seg> segs;
ll sum[200001];
ll sum2[200001];
vector<pll> end_events[200001];
priority_queue<pll> pq;
int max_ind;
ll max_d;

bool solve(ll f, ll k)
{
    pq = {};
    ll cur_del = 0;
    vector<seg> rev;
    vector<pll> del;
    rep(i,max_ind+1)
    {
        ll ile_del = max(0LL,(sum[i]-k+(f-sum[i]+k+1)/2)-cur_del);
      //  cerr << i << " " << ile_del << " " << k << " " << f << " " << siz(end_events[i]) << " del\n";
        forall(it,end_events[i]) pq.push(it);
        cur_del += ile_del;
        while(ile_del > 0 && siz(pq) > 0)
        {
            pll t = pq.top();
            pq.pop();
            if(ile_del - segs[t.ss].c >= 0)
            {
                rev.pb(segs[t.ss]);
                ile_del -= segs[t.ss].c;
            }
            else
            {
                rev.pb({segs[t.ss].l,segs[t.ss].r,ile_del});
                segs[t.ss].c -= ile_del;
                del.pb({t.ss,ile_del});
                pq.push({segs[t.ss].r,t.ss});
                ile_del = 0;
            }
        }
        if(ile_del != 0) 
        {
            forall(it,del)
            {
                segs[it.ff].c += it.ss;
            }
            return 0;
        }
    }
    forall(it,del)
    {
        segs[it.ff].c += it.ss;
    }
    rep(i,n) sum2[i] = 0;
    forall(it,rev)
    {
        sum2[0] += it.c;
        sum2[it.l] += -2*it.c;
        sum2[it.r+1] += 2*it.c;
    }
    ll cur_sum = 0;
    rep(i,n)
    {
        cur_sum += sum2[i];
        sum2[i] = cur_sum;
    }
    rep(i,n)
    {
        if(sum[i]+sum2[i] > k) return 0;
    }
    return 1;
}

bool check(ll k)
{
    if(max_d <= k) return 1;
    return solve(max_d-k,k) || solve(max_d-k+1,k);
}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //random_start();
    cin >> n >> m;
    rep(i,m)
    {
        int a,b,c;
        cin >> a >> b >> c;
        if(a > b) swap(a,b);
        a--;
        b-=2;
      //  cout << a << " " << b << " " << c << " ab\n";
        segs.pb({a,b,c});
    }
    rep(i,n) end_events[i] = {};
    rep(i,n) sum[i] = 0;
    forall(it,segs)
    {
        sum[it.l]+=it.c;
        sum[it.r+1]-=it.c;
    }
    ll cur_sum = 0;
    rep(i,n)
    {
        cur_sum += sum[i];
        sum[i] = cur_sum;
    }
    pll best = {-1,-1};
    rep(i,n) best = max(best,{sum[i],i});
    rep(i,m)
    {
        if(segs[i].l <= best.ss && segs[i].r >= best.ss) end_events[segs[i].l].pb({segs[i].r,i});
    }
    max_ind = best.ss;
    max_d = best.ff;
  //  cout << max_ind << " " << max_d << " max\n";
    ll l = 0;
    ll r = 1e15;
    ll ans = 0;
    while(l <= r)
    {
        ll mid = (l+r)/2;
        if(check(mid))
        {
            ans = mid;
            r = mid-1;
        }
        else
        {
            l = mid+1;
        }
    }
    cout << ans << "\n";
}

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