Submission #512032

#	Time	Username	Problem	Language	Result	Execution time	Memory
512032		kartel	Po (COCI21_po)	C++14	30 / 70	44 ms	2484 KiB

Main

#include <bits/stdc++.h>
#define pb push_back
#define F first
#define S second
#define sz(x) (int)x.size()
using namespace std;

const int N = 1e5 + 500;

int r[N];
bool mk[N];

int main() {
    int n;
    cin >> n;
    vector <int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    vector <int> b = {a[0]};
    for (int i = 1; i < n; i++) {
        if (a[i] != b.back()) {
            b.pb(a[i]);
        }
    }
    a = b;
    vector <pair <int, int> > st;
    st.pb({-1, sz(a)});
    for (int i = sz(a) - 1; i >= 0; i--) {
        while (sz(st) && st.back().F > a[i]) {
            st.pop_back();
        }
        r[i] = st.back().S;
        st.pb({a[i], i});
    }
    n = sz(a);
    int ans = 0;
    for (int i = 0; i < n; i++) {
        if (mk[i] || !a[i]) {
            continue;
        }
        ans++;
        mk[r[i] - 1] = 1;
    }
    cout << ans;
}

• Subtask 1: 30 / 70