Submission #38219

#	Time	Username	Problem	Language	Result	Execution time	Memory
38219		Talant	Money (IZhO17_money)	C++14	100 / 100	296 ms	13732 KiB

money

#include <bits/stdc++.h>

#define fr first
#define sc second
#define OK puts("OK");
#define pb push_back
#define mk make_pair

using namespace std;

typedef long long ll;

const ll inf = (ll)1e9 + 7;
const int N = (int)1e6 + 1;

int n;
int b[N + 5],a[N + 5],t[N + 5],lst = 1,id = 1;
int ans;

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

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

int main () {
        scanf ("%d", &n);

        for (int i = 1; i <= n; i ++)
                scanf ("%d", &b[i]);

        for (int i = 1; i <= n; i ++) {
                if (b[i - 1] != b[i])
                        a[id] = b[i],id ++;
        }
        n = id - 1;

        for (int i = 2; i <= n; i ++) {
                if (a[i] >= a[i - 1]) {
                        int o = get(a[i] - 1) - get(a[lst]);
                        if (o) {
                                for (int j = lst; j < i; j ++)
                                        update (a[j]);
                                lst = i;
                                ans ++;
                        }
                }
                else {
                        for (int j = lst; j < i; j ++)
                                update (a[j]);
                        lst = i;
                        ans ++;
                }
        }
        ans ++;

        cout << ans << endl;
}
/**
6
3 6 4 5 1 2
**/

Compilation message (stderr)

money.cpp: In function 'int main()':
money.cpp:33:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ("%d", &n);
                         ^
money.cpp:36:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
                 scanf ("%d", &b[i]);
                                    ^

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