Submission #832167

#	Time	Username	Problem	Language	Result	Execution time	Memory
832167		That_Salamander	Fish 2 (JOI22_fish2)	C++17	0 / 100	43 ms	17576 KiB

fish2

#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
• Subtask 2: 0 / 8
• Subtask 3: 0 / 12
• Subtask 4: 0 / 23
• Subtask 5: 0 / 35
• Subtask 6: 0 / 17