Submission #38269

#	Time	Username	Problem	Language	Result	Execution time	Memory
38269		Just_Solve_The_Problem	Money (IZhO17_money)	C++11	100 / 100	296 ms	9828 KiB

money

#include <bits/stdc++.h>

using namespace std;

const int N = (int)1e6 + 7;

int a[N], tree[N], n, ans;

void upd (int pos) {
    for (; pos < N; pos += pos & -pos) {
        tree[pos]++;
    }
}

int get (int r) {
    int res = 0;
    for (; r > 0; r -= r & -r) {
        res += tree[r];
    }
    return res;
}

main () {
    scanf ("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf ("%d", &a[i]);
    }
    for (int i = 2, pos = 1; i <= n; i++) {
        if (a[i - 1] > a[i] || get(a[i] - 1) - get(a[pos]) > 0) {
            ans++;
            while (pos < i) upd(a[pos++]);
        }
    }
    cout << ans + 1;
}

Compilation message (stderr)

money.cpp:23:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () {
       ^
money.cpp: In function 'int main()':
money.cpp:24:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d", &n);
                     ^
money.cpp:26:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ("%d", &a[i]);
                            ^

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