oj.uz

Submission #494978

# Submission time Handle Problem Language Result Execution time Memory
494978 2021-12-17T18:53:06 Z lukameladze Money (IZhO17_money) C++14
0 / 100
 1 ms 204 KB 
# include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
using namespace std;
const int N = 1e6 + 5;
int n,a[N],dp[N],curle,pr[N],tree[4*N];
void update(int node, int le, int ri ,int idx, int val) {
    if (le > idx || ri < idx) return ;
    if (le == ri) {
        tree[node] = val;
        return ;
    }
    int mid = (le + ri) / 2;
    update(2*node,le,mid,idx,val);
    update(2*node + 1, mid + 1, ri,idx,val);
    tree[node] = tree[2*node] + tree[2*node + 1];
}
int getans(int node, int le, int ri, int start, int end) {
    if (le > end || ri < start) return 0;
    if (le >= start && ri <= end) return tree[node];
    int mid = (le + ri ) /2;
    return getans(2*node, le,mid,start,end) + getans(2*node + 1, mid + 1, ri, start,end);
}
main() {
    cin>>n;
    for (int i = 1; i <= n; i++) {
        cin>>a[i];
    }
    a[0] = 1e9 + 1;
    for (int i = 1; i <= n; i++) {
        if (a[i] >= a[i - 1]) pr[i] = pr[i - 1];
        else pr[i] = i;
    }
    curle = 1;
    for (int i = 1; i <= n; i++) {
        while(curle < i) {
            if (pr[i] > curle) {
                update(1,1,n,a[curle],1);
                curle++;
                continue;
            }
            if (a[curle] + 1 > a[i] - 1 || getans(1,1,n,a[curle] + 1, a[i] - 1) == 0){
                break;
            }
            update(1,1,n,a[curle],1);
            curle++;
        }
        //cout<<i<<" "<<curle<<endl;
        dp[i] = dp[curle - 1] + 1;
    }
    cout<<dp[n]<<endl;
    
}

Compilation message

money.cpp:25:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   25 | main() {
      | ^~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Incorrect 0 ms 204 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Incorrect 0 ms 204 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Incorrect 0 ms 204 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Incorrect 0 ms 204 KB Output isn't correct
11 Halted 0 ms 0 KB -