oj.uz

Submission #85024

# Submission time Handle Problem Language Result Execution time Memory
85024 2018-11-18T06:40:28 Z muradeyn Money (IZhO17_money) C++14
0 / 100
 2 ms 776 KB 
/* Murad Eynizade */

#include <bits/stdc++.h>
#define intt long long
#define FAST_READ ios_base::sync_with_stdio(0);cin.tie(0);
#define SIZE 1000001
#define INF INT_MAX
#define F first
#define S second
#define in(a) scanf("%d",&a);
#define outn(a) printf("%d\n",&a);
#define outs(a) printf("%d ",&a);
#define MOD 1000000007

using namespace std;

int n , a[SIZE] , co = 1 , tree[4 * SIZE];

set<int>st;

void update(int v,int l,int r,int in) {
    if (l == r) {
        tree[v] = 1;
        return;
    }
    int m = (l + r) >> 1;
    if (in <= m)update(v << 1,l,m,in);
    else update(v << 1 | 1,m + 1,r,in);
    tree[v] = tree[v << 1] + tree[v << 1 | 1];
}

int getans(int v,int l,int r,int le,int ri) {
    if (l > ri || r < le)return 0;
    if (l >= le && r <= ri)return tree[v];
    int m = (l + r) >> 1;
    return getans(v << 1,l,m,le,ri) + getans(v << 1 | 1,m + 1,r,le,ri);
}

int main()
{
    FAST_READ;
    cin>>n;
    for (int i = 1;i<=n;i++)cin>>a[i];
    update(1,1,SIZE,a[1]);
    for (int i = 2;i<=n;i++) {
        if (a[i] == a[i - 1] + 1) {
            if (st.size() >= 2) {
                co++;
                st.clear();
                if (getans(1,1,SIZE,a[i],a[i]))st.insert(a[i]);
            }
            else {
                if (getans(1,1,SIZE,a[i],a[i]))st.insert(a[i]);
            update(1,1,SIZE,a[i]);
                continue;
            }
        }
        else if (a[i] < a[i - 1]) {
            co++;
            st.clear();
            if (getans(1,1,SIZE,a[i],a[i]))st.insert(a[i]);
        }
        else if (getans(1,1,SIZE,a[i - 1] + 1,a[i] - 1)) {
            co++;
            st.clear();
            if (getans(1,1,SIZE,a[i],a[i]))st.insert(a[i]);
        }
        update(1,1,SIZE,a[i]);
    }
    //if (co == 1)co = 0;
    cout<<co<<endl;
    return 0;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 500 KB Output is correct
3 Correct 2 ms 500 KB Output is correct
4 Correct 2 ms 500 KB Output is correct
5 Correct 2 ms 500 KB Output is correct
6 Correct 2 ms 500 KB Output is correct
7 Correct 2 ms 632 KB Output is correct
8 Correct 2 ms 644 KB Output is correct
9 Correct 2 ms 776 KB Output is correct
10 Correct 2 ms 776 KB Output is correct
11 Correct 2 ms 776 KB Output is correct
12 Incorrect 2 ms 776 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 500 KB Output is correct
3 Correct 2 ms 500 KB Output is correct
4 Correct 2 ms 500 KB Output is correct
5 Correct 2 ms 500 KB Output is correct
6 Correct 2 ms 500 KB Output is correct
7 Correct 2 ms 632 KB Output is correct
8 Correct 2 ms 644 KB Output is correct
9 Correct 2 ms 776 KB Output is correct
10 Correct 2 ms 776 KB Output is correct
11 Correct 2 ms 776 KB Output is correct
12 Incorrect 2 ms 776 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 500 KB Output is correct
3 Correct 2 ms 500 KB Output is correct
4 Correct 2 ms 500 KB Output is correct
5 Correct 2 ms 500 KB Output is correct
6 Correct 2 ms 500 KB Output is correct
7 Correct 2 ms 632 KB Output is correct
8 Correct 2 ms 644 KB Output is correct
9 Correct 2 ms 776 KB Output is correct
10 Correct 2 ms 776 KB Output is correct
11 Correct 2 ms 776 KB Output is correct
12 Incorrect 2 ms 776 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 500 KB Output is correct
3 Correct 2 ms 500 KB Output is correct
4 Correct 2 ms 500 KB Output is correct
5 Correct 2 ms 500 KB Output is correct
6 Correct 2 ms 500 KB Output is correct
7 Correct 2 ms 632 KB Output is correct
8 Correct 2 ms 644 KB Output is correct
9 Correct 2 ms 776 KB Output is correct
10 Correct 2 ms 776 KB Output is correct
11 Correct 2 ms 776 KB Output is correct
12 Incorrect 2 ms 776 KB Output isn't correct
13 Halted 0 ms 0 KB -