Submission #36707

#	Time	Username	Problem	Language	Result	Execution time	Memory
36707		Tenuun	Money (IZhO17_money)	C++14	0 / 100	0 ms	9828 KiB

money

#include <bits/stdc++.h>

using namespace std;

long long fen[1000001], n;

void update(int pos, int val){
	for(int i=pos; i<=n; i+= i&-i)
		fen[i]+=val;
}

int sum(int pos){
	long long ans=0;
	for(int i=pos; i>0; i-= i&-i)
		ans+=fen[i];
	return ans;
}

int main(){
	int i, res, last, curr; 
	cin >> n;
	int a[n];
	for(i=1; i<=n; i++)
		cin >> a[i];
	update(2, a[1]);   
	res=1;
	last=a[1];
	for(i=2; i<=n; i++){
		curr=a[i];
		if(curr<last || (sum(curr)-sum(last+1)>0)) res++;
		update(i+1, 1);
		last=curr;	
	}
	cout << res;
	return 0;
}

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