oj.uz

Submission #567388

# Submission time Handle Problem Language Result Execution time Memory
567388 2022-05-23T11:45:20 Z jeff Fish 2 (JOI22_fish2) C++14
31 / 100
 585 ms 24044 KB 
#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;}
    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

fish2.cpp: In function 'void qv(long long int, long long int, long long int, long long int)':
fish2.cpp:69: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]
   69 |     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:84: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]
   84 |         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:96:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |     scanf("%lld", &N);
      |     ~~~~~^~~~~~~~~~~~
fish2.cpp:98:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   98 |     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:106:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |     scanf("%lld", &Q);
      |     ~~~~~^~~~~~~~~~~~
fish2.cpp:108:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |         scanf("%lld %lld %lld", &t, &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 5 ms 9668 KB Output is correct
4 Correct 6 ms 9684 KB Output is correct
5 Incorrect 7 ms 9684 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 67 ms 21420 KB Output is correct
3 Correct 87 ms 21336 KB Output is correct
4 Correct 86 ms 21424 KB Output is correct
5 Correct 71 ms 21208 KB Output is correct
6 Correct 60 ms 20292 KB Output is correct
7 Correct 52 ms 20080 KB Output is correct
8 Correct 60 ms 20368 KB Output is correct
9 Correct 74 ms 20144 KB Output is correct
10 Correct 58 ms 20340 KB Output is correct
11 Correct 59 ms 20344 KB Output is correct
12 Correct 53 ms 20328 KB Output is correct
13 Correct 58 ms 20280 KB Output is correct
14 Correct 71 ms 21020 KB Output is correct
15 Correct 70 ms 20980 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 5 ms 9668 KB Output is correct
4 Correct 6 ms 9684 KB Output is correct
5 Incorrect 7 ms 9684 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 67 ms 21420 KB Output is correct
3 Correct 87 ms 21336 KB Output is correct
4 Correct 86 ms 21424 KB Output is correct
5 Correct 71 ms 21208 KB Output is correct
6 Correct 60 ms 20292 KB Output is correct
7 Correct 52 ms 20080 KB Output is correct
8 Correct 60 ms 20368 KB Output is correct
9 Correct 74 ms 20144 KB Output is correct
10 Correct 58 ms 20340 KB Output is correct
11 Correct 59 ms 20344 KB Output is correct
12 Correct 53 ms 20328 KB Output is correct
13 Correct 58 ms 20280 KB Output is correct
14 Correct 71 ms 21020 KB Output is correct
15 Correct 70 ms 20980 KB Output is correct
16 Correct 6 ms 9684 KB Output is correct
17 Correct 497 ms 21536 KB Output is correct
18 Correct 395 ms 23956 KB Output is correct
19 Correct 458 ms 23528 KB Output is correct
20 Correct 447 ms 23564 KB Output is correct
21 Correct 435 ms 23344 KB Output is correct
22 Correct 488 ms 24044 KB Output is correct
23 Correct 394 ms 23180 KB Output is correct
24 Correct 518 ms 23388 KB Output is correct
25 Correct 447 ms 23400 KB Output is correct
26 Correct 518 ms 23412 KB Output is correct
27 Correct 238 ms 23148 KB Output is correct
28 Correct 264 ms 23220 KB Output is correct
29 Correct 246 ms 23332 KB Output is correct
30 Correct 386 ms 22044 KB Output is correct
31 Correct 398 ms 21824 KB Output is correct
32 Correct 580 ms 22360 KB Output is correct
33 Correct 364 ms 22744 KB Output is correct
34 Correct 585 ms 22224 KB Output is correct
35 Correct 369 ms 21940 KB Output is correct
36 Correct 526 ms 22968 KB Output is correct
37 Correct 252 ms 22252 KB Output is correct
38 Correct 250 ms 22192 KB Output is correct
39 Correct 284 ms 23572 KB Output is correct
40 Correct 225 ms 23420 KB Output is correct

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 67 ms 21420 KB Output is correct
3 Correct 87 ms 21336 KB Output is correct
4 Correct 86 ms 21424 KB Output is correct
5 Correct 71 ms 21208 KB Output is correct
6 Correct 60 ms 20292 KB Output is correct
7 Correct 52 ms 20080 KB Output is correct
8 Correct 60 ms 20368 KB Output is correct
9 Correct 74 ms 20144 KB Output is correct
10 Correct 58 ms 20340 KB Output is correct
11 Correct 59 ms 20344 KB Output is correct
12 Correct 53 ms 20328 KB Output is correct
13 Correct 58 ms 20280 KB Output is correct
14 Correct 71 ms 21020 KB Output is correct
15 Correct 70 ms 20980 KB Output is correct
16 Correct 6 ms 9684 KB Output is correct
17 Incorrect 521 ms 21744 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 5 ms 9668 KB Output is correct
4 Correct 6 ms 9684 KB Output is correct
5 Incorrect 7 ms 9684 KB Output isn't correct
6 Halted 0 ms 0 KB -