oj.uz

Submission #802794

# Submission time Handle Problem Language Result Execution time Memory
802794 2023-08-02T14:35:23 Z Johann Mizuyokan 2 (JOI23_mizuyokan2) C++14
0 / 100
 4000 ms 51224 KB 
#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 int INF = 1e9;

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];
        }
}

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 = -INF;
        // assume we start with a minimum
        {
            int tmp = b - 1;
            int 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
            if (a <= vor[tmp])
                ++mini;
            ans = mini;
        }

        // 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
                    if (a <= vor[tmp])
                        ++mini;
                    ans = max(ans, mini);
                    break;
                }
            }
        }

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

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Incorrect 1 ms 340 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Incorrect 1 ms 340 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Incorrect 1 ms 340 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 94 ms 40248 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Execution timed out 4066 ms 51224 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Incorrect 1 ms 340 KB Output isn't correct
12 Halted 0 ms 0 KB -