Submission #1153825

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153825		itslq	Po (COCI21_po)	C++20	20 / 70	34 ms	2376 KiB

Main

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

const int MAXN = 1e5;
set<int> modified;
vector<int> pa(MAXN), rk(MAXN), vis(MAXN);

int C = 0;

int root(int n) {
    if (pa[n] == n) return n;
    return pa[n] = root(pa[n]);
}

void merge(int x, int y) {
    int a = root(x), b = root(y);
    if (a == b) return;
    if (rk[a] < rk[b]) {
        pa[a] = b;
        if (modified.find(a) != modified.end()) modified.erase(a);
        modified.insert(b);
    } else if (rk[a] > rk[b]){
        pa[b] = a;
        if (modified.find(b) != modified.end()) modified.erase(b);
        modified.insert(a);
    } else {
        pa[a] = b;
        rk[b]++;
        if (modified.find(a) != modified.end()) modified.erase(a);
        modified.insert(b);
    }
}

int main() {
    int N, P = INT_MAX, A = 0, ind, C = 0;
    cin >> N;
    vector<pair<int, int>> H(N);

    for (int i = 0; i < N; i++) {
        pa[i] = H[i].second = i;
        cin >> H[i].first;
    }

    sort(H.begin(), H.end(), greater<pair<int, int>>());

    for (int i = 0; i < N; i++) {
        if (P != H[i].first) {
            A += modified.size();
            modified.clear();
            P = H[i].first;
        }

        ind = H[i].second;
        vis[ind] = 1;
        modified.insert(ind);
        if (ind && vis[ind - 1]) merge(ind, ind - 1);
        if (ind != N - 1 && vis[ind + 1]) merge(ind, ind + 1);
    }

    cout << A + modified.size();
}

• Subtask 1: 20 / 70