Submission #36857

#	Time	Username	Problem	Language	Result	Execution time	Memory
36857		top34051	Money (IZhO17_money)	C++14	100 / 100	286 ms	9828 KiB

money

#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e6 + 5;

int n;
int a[maxn], tree[maxn+5];

int sum(int x) {
    int res = 0;
    while(x>0) {
        res += tree[x];
        x -= x&-x;
    }
    return res;
}

void add(int x,int val) {
    while(x<=maxn) {
        tree[x] += val;
        x += x&-x;
    }
}

int main() {
    int l,r,ans = 0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++) {
        l = r = i;
        while(a[r+1]>=a[r] && sum(a[r+1]-1)-sum(a[l])<=0) r++;
        ans++;
        while(l<=r) add(a[l++],1);
        i = r;
    }
    printf("%d",ans);
}

Compilation message (stderr)

money.cpp: In function 'int main()':
money.cpp:27:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
                   ^
money.cpp:28:44: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=1;i<=n;i++) scanf("%d",&a[i]);
                                            ^

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