oj.uz

Submission #251665

# Submission time Handle Problem Language Result Execution time Memory
251665 2020-07-22T06:57:02 Z VEGAnn Baloni (COCI15_baloni) C++14
0 / 100
 2000 ms 52472 KB 
#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define i2 array<int,2>
using namespace std;
typedef long long ll;
const int N = 1000100;
const int C = 22;
const int md = 10007;
set<i2> st;
int n, a[N], ans, nt[N], pos[N];

int mult(int x, int y) { return (x * y) % md; }

void SUM(int &x, int y){
    x += y;
    if (x >= md)
        x -= md;
}

int main() {
#ifdef _LOCAL
    freopen("in.txt","r",stdin); // freopen("output.txt","w",stdout);
#else
//    freopen("mining.in","r",stdin); freopen("mining.out","w",stdout);
    ios_base::sync_with_stdio(0); cin.tie(0);
#endif

    cin >> n;

    for (int i = 1; i <= n; i++)
        cin >> a[i];

    for (int i = n; i > 0; i--){
        nt[i] = pos[a[i] - 1];
        pos[a[i]] = i;
        st.insert({a[i], i});
    }

    while (sz(st) > 0){
        ans++;

        i2 cr = (*(--st.end()));

        st.erase(cr);

        int ps = nt[cr[1]];

        while (ps != 0){
            st.erase({a[ps], ps});
            ps = nt[ps];
        }
    }

    cout << ans;

    return 0;
}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Incorrect 1 ms 512 KB Output isn't correct
3 Incorrect 2 ms 640 KB Output isn't correct
4 Incorrect 3 ms 640 KB Output isn't correct
5 Execution timed out 2071 ms 47292 KB Time limit exceeded
6 Execution timed out 2100 ms 52472 KB Time limit exceeded
7 Execution timed out 2099 ms 43256 KB Time limit exceeded
8 Execution timed out 2087 ms 42744 KB Time limit exceeded
9 Execution timed out 2091 ms 45404 KB Time limit exceeded
10 Execution timed out 2088 ms 46928 KB Time limit exceeded