Submission #319226

#	Time	Username	Problem	Language	Result	Execution time	Memory
319226		dolphingarlic	Money (IZhO17_money)	C++14	100 / 100	251 ms	15000 KiB

money

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

int n, a[1000005], bit[1000005];

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

int query(int a) {
	int ans = 0;
	for (; a; a -= (a & (-a))) ans += bit[a];
	return ans;
}

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) scanf("%d", a + i);
	int ans = 0;
	update(a[0]);
	for (int i = 0; i < n;) {
		int j = i++;
		ans++;
		while (i < n && query(a[i] - 1) <= query(a[j]) && a[i] >= a[i - 1]) i++;
		for (int k = j; k < i; k++) update(a[k]);
	}
	printf("%d", ans);
	return 0;
}

Compilation message (stderr)

money.cpp: In function 'int main()':
money.cpp:15:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   15 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
money.cpp:16:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   16 |  for (int i = 0; i < n; i++) scanf("%d", a + i);
      |                              ~~~~~^~~~~~~~~~~~~

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