oj.uz

Submission #512044

# Submission time Handle Problem Language Result Execution time Memory
512044 2022-01-16T06:18:58 Z kartel Po (COCI21_po) C++14
30 / 70
 69 ms 6756 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;
    map <int, int> used;
    for (int i = 0; i < n; i++) {
        if (mk[i] || !a[i] || (used.count(a[i]) && used[a[i]] <= i)) {
            continue;
        }
        ans++;
        used[a[i]] = r[i] - 1;
    }
    cout << ans;
}

Subtask #1
30.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 10 ms 968 KB Output isn't correct
5 Incorrect 16 ms 1240 KB Output isn't correct
6 Correct 60 ms 4140 KB Output is correct
7 Correct 69 ms 6756 KB Output is correct