Submission #198567

#	Time	Username	Problem	Language	Result	Execution time	Memory
198567		combi1k1	Arranging Tickets (JOI17_arranging_tickets)	C++14	0 / 100	8 ms	4984 KiB

arranging_tickets

#include<bits/stdc++.h>

using namespace std;

#define ll  long long
#define ld  double

#define sz(x)   (int)x.size()
#define all(x)  x.begin(),x.end()

#define pb  emplace_back
#define X   first
#define Y   second

const int   N   = 2e5 + 5;

typedef pair<int,int>   ii;

vector<ii>  g[N];
ll  s[N], z[N];
ll  h[N], t[N];

int main()  {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n;  cin >> n;
    int q;  cin >> q;

    for(int i = 0 ; i < q ; ++i)    {
        int l;  cin >> l;
        int r;  cin >> r;
        int x;  cin >> x;

        if (l > r)  swap(l,r);

        g[l].pb(r,x);
        s[l] += x;
        s[r] -= x;
    }
    ll  mx = -1;
    int ps = 0;

    for(int i = 1 ; i <= n ; ++i)   {
        s[i] += s[i - 1];
        if (mx < s[i])
            mx = s[i],
            ps = i;
    }
    for(int i = 1 ; i <= ps ; ++i)  z[i] = max(z[i - 1],s[i]);
    for(int i = n ; i >= ps ; --i)  z[i] = max(z[i + 1],s[i]);

    auto check = [&](ll  x) {
        ll  sum = 0;

        for(int i = 0 ; i < n ; ++i)
            h[i] = min(h[i],x),
            t[i] = 0;

        h[ps] = 0;
        priority_queue<ii>  pq;

        for(int i = 1 ; i <= ps ; ++i)  {
            for(ii  e : g[i])
                if (e.X > ps)   pq.push(e);

            sum += h[i - 1] - h[i];

            while (1)   {
                if (pq.empty()) return  0;

                int p = pq.top().X;
                int c = pq.top().Y;

                pq.pop();

                if (c >= sum)   {
                    c -= sum;
                    t[p] -= sum;
                    pq.push(ii(p,c));
                    sum = 0;
                    break;
                }
                else    {
                    sum  -= c;
                    t[p] -= c;
                }
            }
        }
        for(int i = 1 ; i < n ; ++i)   {
            t[i] += t[i - 1];
            if (h[i] + t[i] < 0)
                return 0;
        }
        return  1;
    };
    auto chk = [&](ll  M)   {
        for(int i = 0 ; i < 2 ; ++i)    {
            ll  x = z[ps] - M + i;

            for(int j = 0 ; j < n ; ++j)
                h[j] = (x + M - z[j]) / 2;

            if (h[0] < x)   continue;
            if (check(x))   return  1;
        }
        return  0;
    };

    ll  L = 0;
    ll  R = mx;

    while(L < R)    {
        ll  M = L + R >> 1;

        if (chk(M))
            R = M;
        else
            L = M + 1;
    }
    cout << L << endl;
}

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