제출 #512027

#제출 시각아이디문제언어결과실행 시간메모리
512027kartelPo (COCI21_po)C++14
20 / 70
44 ms3476 KiB
#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]) {
            continue;
        }
        ans += (a[i] > 0);
        mk[r[i] - 1] = 1;
    }
    cout << ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...