Submission #50305

#	Time	Username	Problem	Language	Result	Execution time	Memory
50305		mra2322001	Money (IZhO17_money)	C++14	45 / 100	1533 ms	152264 KiB

money

#include <bits/stdc++.h>
#define f0(i, n) for(int i(0); i<(n); i++)
#define f1(i, n) for(int i(1); i<=(n); i++)

using namespace std;
typedef long long ll;
const int N = 1e6 + 5;

int n, a[N], f[N];
set <int> s;

int solve(int u, int sl){
    if(u== n + 1) return printf("%d", sl), 0;
    int v = f[u];
    int l = u, r = v, ans = u;
    while(l <= r){
        int mid = (l + r)/2;
        auto it = s.lower_bound(a[mid]);
        --it;
        if(*it <= a[u]) l = mid + 1, ans = mid;
        else r = mid - 1;
    }
    for(int i = u; i <= ans; i++) s.insert(a[i]);
    solve(ans + 1, sl + 1);
}

int main(){
    ios_base::sync_with_stdio(0);

    scanf("%d", &n);
    f1(i, n) scanf("%d", &a[i]);
    for(int i = n; i >= 1; i--){
        if(i==n) f[i] = n;
        else{
            if(a[i] <= a[i + 1]) f[i] = f[i + 1];
            else f[i] = i;
        }
    }
    s.insert(0); s.insert(1e6 + 5);
    solve(1, 0);
}

Compilation message (stderr)

money.cpp: In function 'int solve(int, int)':
money.cpp:25:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
money.cpp: In function 'int main()':
money.cpp:30:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
money.cpp:31:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     f1(i, n) scanf("%d", &a[i]);
              ~~~~~^~~~~~~~~~~~~

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