Submission #802842

#	Time	Username	Problem	Language	Result	Execution time	Memory
802842		Johann	Mizuyokan 2 (JOI23_mizuyokan2)	C++14	60 / 100	4035 ms	85740 KiB

mizuyokan2

#include "bits/stdc++.h"
using namespace std;

typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll, ll> pii;
typedef vector<pii> vpii;
typedef vector<vpii> vvpii;
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

const ll INF = 1e18;

int N, Q;
vi L;
vi pref;
vi vor, nach;
vvi lift;
vi vorg;

void precompute()
{
    pref.resize(sz(L));
    partial_sum(all(L), pref.begin());

    vor.resize(N);  // the last possible minima, like [0, vor[i]) with exclusive border
    nach.resize(N); // the next possible minima , like [nach[i], end) with inclusive
    for (ll i = 0, needed; i < N; ++i)
    {
        // vor
        needed = pref[i] - 2 * L[i] - 1;
        pii ac;
        if (needed < 0)
            vor[i] = -1;
        else
            vor[i] = upper_bound(all(pref), needed) - pref.begin();

        // nach
        needed = pref[i] + L[i] + 1;
        if (needed > pref.back())
            nach[i] = N + 1; // maybe different value, later for the lift array
        else
            nach[i] = lower_bound(all(pref), needed) - pref.begin() + 1; // something in [1, N]
    }
    lift.assign(ceil(log2(N)), vi(N + 2, -1));

    vvi todo(N + 2);
    for (int i = 0; i < sz(lift[0]); ++i)
    {
        if (i > 0)
            lift[0][i] = max(lift[0][i], lift[0][i - 1]);
        for (ll x : todo[i])
        {
            if (i >= sz(vor) || x < vor[i])
                lift[0][i] = max(lift[0][i], x);
            else
                todo[i + 1].push_back(x);
        }
        if (i < sz(nach))
            todo[nach[i]].push_back(i);
    }

    for (int j = 1; j < sz(lift); ++j)
        for (int i = 0; i < sz(lift[j]); ++i)
        {
            int step = lift[j - 1][i];
            lift[j][i] = (step == -1) ? -1 : lift[j - 1][step];
        }
    for (int j = 1; j < sz(lift); ++j)
        for (int i = 0; i < sz(lift[j]) - 1; ++i)
            assert(lift[j][i] <= lift[j][i + 1]);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> N;
    L.resize(N);
    for (int i = 0; i < N; ++i)
        cin >> L[i];
    cin >> Q;

    precompute();

    while (Q--)
    {
        ll x, y, a, b;
        cin >> x >> y >> a >> b;
        --x;
        if (L[x] != y)
        {
            L[x] = y;
            precompute();
        }

        ll ans = 1;
        // assume we start with a minimum
        {
            int tmp = b - 1;
            ll mini = 0; // how many steps
            for (int j = sz(lift) - 1; j >= 0; --j)
                if (lift[j][tmp] >= a)
                    tmp = lift[j][tmp], mini += 1 << j;
            mini = 2 * mini + 1; // how many segments in total
            ans = max(ans, mini);
            for (; tmp > a; --tmp)
            {
                if (a <= vor[tmp])
                    ans = max(ans, mini + 1);
            }
        }

        // assume we start with a maximum
        {
            ll buffer = 0;
            for (int i = b - 1; i > a; --i)
            {
                buffer += L[i];
                if (L[i - 1] < buffer)
                {
                    int tmp = i - 1;
                    ll mini = 0; // how many steps
                    for (int j = sz(lift) - 1; j >= 0; --j)
                        if (lift[j][tmp] >= a)
                            tmp = lift[j][tmp], mini += 1 << j;
                    mini = 2 * mini + 2; // how many segments in total
                    ans = max(ans, mini);
                    for (; tmp > a; --tmp)
                    {
                        if (a <= vor[tmp])
                            ans = max(ans, mini + 1);
                    }
                    break;
                }
            }
        }

        cout << ans << "\n";
    }
}

• Subtask 1: 6 / 6
• Subtask 2: 9 / 9
• Subtask 3: 13 / 13
• Subtask 4: 32 / 32
• Subtask 5: 0 / 29
• Subtask 6: 0 / 11