Submission #567398

#	Time	Username	Problem	Language	Result	Execution time	Memory
567398		jeff	Fish 2 (JOI22_fish2)	C++14	100 / 100	599 ms	25676 KiB

fish2

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

long long N, o[100000], fw[100001], pA[400000], mC[400000];
pair<long long, long long> mA[400000];
vector<pair<long long, long long> > vA[400000];
stack<long long> s;

long long qf(long long i) {long long t = 0; while (i) t += fw[i], i -= i & -i; return t;}
void uf(long long i, long long v) {while (i < 100001) fw[i] += v, i += i & -i;}

long long qpl(long long i, long long p, long long v, long long l, long long h) {
    //printf("QPL %lld [%lld] | %lld %lld | %lld %lld\n", i, pA[i], p, v, l, h);
    if (l > p || pA[i] < v) return -1;
    if (l >= h) return l;
    long long c = qpl(i * 2 + 1, p, v, (l + h) / 2 + 1, h);
    if (c > -1) return c;
    return qpl(i * 2, p, v, l, (l + h) / 2);
}

long long qpr(long long i, long long p, long long v, long long l, long long h) {
    //printf("QPR %lld [%lld] | %lld %lld | %lld %lld\n", i, pA[i], p, v, l, h);
    if (h < p || pA[i] < v) return -1;
    if (l >= h) return l;
    long long c = qpr(i * 2, p, v, l, (l + h) / 2);
    if (c > -1) return c;
    return qpr(i * 2 + 1, p, v, (l + h) / 2 + 1, h);
}

void up(long long i, long long p, long long v, long long l, long long h) {
    if (p < l || h < p) return;
    if (p <= l && h <= p) {pA[i] = v; return;}
    up(i * 2, p, v, l, (l + h) / 2);
    up(i * 2 + 1, p, v, (l + h) / 2 + 1, h);
    pA[i] = max(pA[i * 2], pA[i * 2 + 1]);
}

void inm(long long i, long long l, long long h) {
    mA[i] = make_pair(0, h - l + 1);
    if (l >= h) return;
    inm(i * 2, l, (l + h) / 2);
    inm(i * 2 + 1, (l + h) / 2 + 1, h);
}

pair<long long, long long> qm(long long i, long long a, long long b, long long l, long long h) {
    if (b < l || h < a) return make_pair(LLONG_MAX, 0);
    if (a <= l && h <= b) return mA[i];
    if (mC[i]) {mA[i * 2].first += mC[i]; mC[i * 2] += mC[i]; mA[i * 2 + 1].first += mC[i]; mC[i * 2 + 1] += mC[i]; mC[i] = 0;}
    pair<long long, long long> pa = qm(i * 2, a, b, l, (l + h) / 2), pb = qm(i * 2 + 1, a, b, (l + h) / 2 + 1, h);
    if (pa > pb) swap(pa, pb);
    if (pa.first == pb.first) pa.second += pb.second;
    return pa;
}

void um(long long i, long long a, long long b, long long v, long long l, long long h) {
    //printf("UM %lld | %lld %lld (%lld) | %lld %lld <- [%lld %lld]\n", i, a, b, v, l, h, mA[i].first, mA[i].second);
    if (b < l || h < a) return;
    if (a <= l && h <= b) {mA[i].first += v; mC[i] += v; return;}
    if (mC[i]) {mA[i * 2].first += mC[i]; mC[i * 2] += mC[i]; mA[i * 2 + 1].first += mC[i]; mC[i * 2 + 1] += mC[i]; mC[i] = 0;}
    um(i * 2, a, b, v, l, (l + h) / 2);
    um(i * 2 + 1, a, b, v, (l + h) / 2 + 1, h);
    mA[i] = min(mA[i * 2], mA[i * 2 + 1]);
    if (mA[i * 2].first == mA[i * 2 + 1].first) mA[i].second = mA[i * 2].second + mA[i * 2 + 1].second;
    //printf("UM %lld | %lld %lld (%lld) | %lld %lld -> [%lld %lld]\n", i, a, b, v, l, h, mA[i].first, mA[i].second);
}

void qv(long long i, long long p, long long l, long long h) {
    if (p < l || h < p) return;
    //printf("- QV %lld | %lld | %lld %lld - %lld\n", i, p, l, h, (l + h) / 2);
    for (long long j = 0; j < vA[i].size(); ++j) if (vA[i][j].first <= p && p <= vA[i][j].second && min(o[vA[i][j].first], o[vA[i][j].second]) <= qf(vA[i][j].second) - qf(vA[i][j].first + 1)) {
        um(1, vA[i][j].first + 1, vA[i][j].second - 1, -1, 0, N - 1);
        swap(vA[i][j], vA[i].back());
        vA[i].pop_back();
        --j;
    }
    qv(i * 2, p, l, (l + h) / 2 - 1);
    qv(i * 2 + 1, p, (l + h) / 2 + 1, h);
}

void uv(long long i, long long a, long long b, long long l, long long h) {
    if (a + 1 == b) return;
    //printf("- UV %lld | %lld %lld | %lld %lld - %lld\n", i, a, b, l, h, (l + h) / 2);
    if (b < l || h < a) return;
    if (a <= (l + h) / 2 && (l + h) / 2 <= b) {
        for (long long j = 0; j < vA[i].size(); ++j) if (a == vA[i][j].first && b == vA[i][j].second) return;
        um(1, a + 1, b - 1, 1, 0, N - 1);
        vA[i].emplace_back(a, b);
        return;
    }
    uv(i * 2, a, b, l, (l + h) / 2 - 1);
    uv(i * 2 + 1, a, b, (l + h) / 2 + 1, h);
}

int main() {
    //freopen("in.txt", "r", stdin);
    long long Q, t, a, b, l, h, i, j;
    scanf("%lld", &N);
    inm(1, 0, N - 1);
    for (i = 0; i < N; ++i) scanf("%lld", &o[i]), uf(i + 1, o[i]), up(1, i, o[i], 0, N - 1);
    for (i = 0; i < N; ++i) {
        while (!s.empty() && o[s.top()] <= o[i]) {if (o[s.top()] > qf(i) - qf(s.top() + 1)) uv(1, s.top(), i, 0, N - 1); s.pop();}
        if (!s.empty() && o[i] > qf(i) - qf(s.top() + 1)) uv(1, s.top(), i, 0, N - 1);
        s.push(i);
    }
    //printf("\nQ\n\n");
    //for (j = 0; j < N; ++j) printf("%lld%c", qm(1, j, j, 0, N - 1).first, j < N - 1 ? ' ' : '\n');
    scanf("%lld", &Q);
    for (i = 0; i < Q; ++i) {
        scanf("%lld %lld %lld", &t, &a, &b);
        --a;
        if (t == 1) {
            uf(a + 1, b - o[a]);
            up(1, a, b, 0, N - 1);
            if (o[a] < b) {
                o[a] = b;
                qv(1, a, 0, N - 1);
                for (l = a - 1; l > -1; l = qpl(1, l - 1, qf(a) - qf(l) + 1, 0, N - 1)) {
                    if (min(o[l], o[a]) > qf(a) - qf(l + 1)) uv(1, l, a, 0, N - 1);
                    if (o[l] >= o[a]) break;
                }
                for (h = a + 1; h > -1; h = qpr(1, h + 1, qf(h + 1) - qf(a + 1) + 1, 0, N - 1)) {
                    if (min(o[a], o[h]) > qf(h) - qf(a + 1)) uv(1, a, h, 0, N - 1);
                    if (o[a] <= o[h]) break;
                }
            } else {
                o[a] = b;
                qv(1, a, 0, N - 1);
                l = qpl(1, a - 1, o[a] + 1, 0, N - 1);
                h = qpr(1, a + 1, o[a] + 1, 0, N - 1);
                while (l > -1 && h > -1) {
                    if (min(o[l], o[h]) > qf(h) - qf(l + 1)) uv(1, l, h, 0, N - 1);
                    if (o[l] < o[h]) l = qpl(1, l - 1, qf(h) - qf(l) + 1, 0, N - 1);
                    else h = qpr(1, h + 1, qf(h + 1) - qf(l + 1) + 1, 0, N - 1);
                }
            }
        } else {
            --b;
            l = a;
            h = b;
            for (j = a; j > -1 && j <= b; j = qpr(1, j + 1, qf(j + 1) - qf(a) + 1, 0, N - 1)) if (o[j] > qf(j) - qf(a)) l = j;
            for (j = b; j >= a; j = qpl(1, j - 1, qf(b + 1) - qf(j) + 1, 0, N - 1)) if (o[j] > qf(b + 1) - qf(j + 1)) h = j;
            //for (j = 0; j < N; ++j) printf("%lld%c", qm(1, j, j, 0, N - 1).first, j < N - 1 ? ' ' : '\n');
            printf("%lld\n", qm(1, l, h, 0, N - 1).second);
        }
    }
    return 0;
}

Compilation message (stderr)

fish2.cpp: In function 'void qv(long long int, long long int, long long int, long long int)':
fish2.cpp:70:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |     for (long long j = 0; j < vA[i].size(); ++j) if (vA[i][j].first <= p && p <= vA[i][j].second && min(o[vA[i][j].first], o[vA[i][j].second]) <= qf(vA[i][j].second) - qf(vA[i][j].first + 1)) {
      |                           ~~^~~~~~~~~~~~~~
fish2.cpp: In function 'void uv(long long int, long long int, long long int, long long int, long long int)':
fish2.cpp:85:33: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |         for (long long j = 0; j < vA[i].size(); ++j) if (a == vA[i][j].first && b == vA[i][j].second) return;
      |                               ~~^~~~~~~~~~~~~~
fish2.cpp: In function 'int main()':
fish2.cpp:97:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |     scanf("%lld", &N);
      |     ~~~~~^~~~~~~~~~~~
fish2.cpp:99:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |     for (i = 0; i < N; ++i) scanf("%lld", &o[i]), uf(i + 1, o[i]), up(1, i, o[i], 0, N - 1);
      |                             ~~~~~^~~~~~~~~~~~~~~
fish2.cpp:107:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |     scanf("%lld", &Q);
      |     ~~~~~^~~~~~~~~~~~
fish2.cpp:109:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |         scanf("%lld %lld %lld", &t, &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 8 / 8
• Subtask 3: 12 / 12
• Subtask 4: 23 / 23
• Subtask 5: 35 / 35
• Subtask 6: 17 / 17