oj.uz

Submission #512032

# Submission time Handle Problem Language Result Execution time Memory
512032 2022-01-16T06:14:00 Z kartel Po (COCI21_po) C++14
30 / 70
 44 ms 2484 KB 
#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.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Incorrect 0 ms 204 KB Output isn't correct
3 Incorrect 1 ms 204 KB Output isn't correct
4 Incorrect 8 ms 968 KB Output isn't correct
5 Incorrect 14 ms 1364 KB Output isn't correct
6 Correct 40 ms 1968 KB Output is correct
7 Correct 44 ms 2484 KB Output is correct