Submission #50308

#	Time	Username	Problem	Language	Result	Execution time	Memory
50308		mra2322001	Money (IZhO17_money)	C++14	45 / 100	1549 ms	101656 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;
    auto it = s.upper_bound(a[u]);
    int x = *it;
    for(int k = u; k <= f[u]; k++){
        if(a[k] > x){
            solve(k, sl + 1);
            return 0;
        }
        else{
            s.insert(a[k]);
        }
    }
    solve(f[u] + 1, sl + 1);
    return 0;
}

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;
        }
    }
    if(f[1]==n){
        cout << 1;
        return 0;
    }
    s.insert(0); s.insert(1e6 + 5);
    solve(1, 0);
}

Compilation message (stderr)

money.cpp: In function 'int solve(int, int)':
money.cpp:15:9: warning: unused variable 'l' [-Wunused-variable]
     int l = u, r = v, ans = u;
         ^
money.cpp:15:16: warning: unused variable 'r' [-Wunused-variable]
     int l = u, r = v, ans = u;
                ^
money.cpp:15:23: warning: unused variable 'ans' [-Wunused-variable]
     int l = u, r = v, ans = u;
                       ^~~
money.cpp: In function 'int main()':
money.cpp:34:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
money.cpp:35: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