oj.uz

Submission #832167

# Submission time Handle Problem Language Result Execution time Memory
832167 2023-08-21T05:31:49 Z That_Salamander Fish 2 (JOI22_fish2) C++17
0 / 100
 43 ms 17576 KB 
#include <bits/stdc++.h>
#define int long long

using namespace std;

#define FOR(v, b) for (int v = 0; v < b; v++)

int n, q;
int sizes[100000];

int component[100000];
vector<int> components[100000];
int componentSizes[100000];
int numValid[100000];

void mergeInto(int a, int b) {
    int ca = component[a];
    int cb = component[b];

    int resValid;
    if (sizes[a] <= componentSizes[cb]) {
        resValid = numValid[ca] + numValid[cb];
    } else {
        resValid = numValid[ca];
    }

    if (components[ca].size() > components[cb].size()) {
        for (int x : components[cb]) {
            components[ca].push_back(x);
            component[x] = ca;
        }

        componentSizes[ca] += cb;
        numValid[ca] = resValid;
    } else {
        for (int x : components[ca]) {
            components[cb].push_back(x);
            component[x] = cb;
        }

        componentSizes[cb] += componentSizes[ca];
        numValid[cb] = resValid;
    }
}

signed main() {
    cin >> n;

    FOR(i, n) { cin >> sizes[i]; }

    /*vector<int> ord(n);
    FOR(i, n) {
        ord[i] = i;
        component[i] = i;
        components[i].push_back(i);
        componentSizes[i] = sizes[i];
    }

    sort(ord.begin(), ord.end(), [&](int a, int b) { return sizes[a] < sizes[b];
    });

    for (int i: ord) {
        if (i != 0 && sizes[i-1] <= sizes[i]) {
            mergeInto(i, i-1);
        }

        if (i != ord.size() - 1 && sizes[i+1] < sizes[i]) {
            mergeInto(i, i+1);
        }
    }

    cout << components[component[ord.back()]].size() << endl;*/

    cin >> q;

    FOR(qi, q) {
        int t, x, y;
        cin >> t >> x >> y;
        if (t == 1) {
            sizes[x - 1] = y;
        } else {
            x--;
            y--;
            vector<int> ord(y - x + 1);

            for (int i = x; i <= y; i++) {
                ord[i - x] = i;
                component[i] = i;
                components[i] = {i};
                componentSizes[i] = sizes[i];
                numValid[i] = 1;
            }

            sort(ord.begin(), ord.end(),
                 [&](int a, int b) { return sizes[a] < sizes[b]; });

            for (int i : ord) {
                if (i != x && sizes[i - 1] <= sizes[i]) {
                    mergeInto(i, i - 1);
                }

                if (i != y && sizes[i + 1] < sizes[i]) {
                    mergeInto(i, i + 1);
                }
            }

#ifdef LOCAL_TEST
            cout << "ANSWER: ";
#endif
            cout << numValid[component[ord.back()]] << endl;
        }
    }
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 43 ms 15812 KB Output is correct
3 Incorrect 37 ms 17576 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

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

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 43 ms 15812 KB Output is correct
3 Incorrect 37 ms 17576 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 43 ms 15812 KB Output is correct
3 Incorrect 37 ms 17576 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

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