Submission #494978

#	Time	Username	Problem	Language	Result	Execution time	Memory
494978		lukameladze	Money (IZhO17_money)	C++14	0 / 100	1 ms	204 KiB

money

# 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 (stderr)

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

• Subtask 1: 0 / 9
• Subtask 2: 0 / 16
• Subtask 3: 0 / 20
• Subtask 4: 0 / 55