Submission #92526

#	Time	Username	Problem	Language	Result	Execution time	Memory
92526		Nodir_Bobiev	Money (IZhO17_money)	C++14	100 / 100	734 ms	8312 KiB

money

// solved by using fenvick tree 
// + binary search

# include <iostream>

using namespace std;

const int N = 1e6 + 100;

int n, ans = 1;
int a[N];
int cnt[N];

void update(int i)
{
	while(i < N){
		cnt[i]++;
		i += (i & -i);
	}
}

int get(int i){
	int ret = 0;
	while(i > 0){
		ret += cnt[i];
		i -= (i & -i);
	}
	return ret;
}

int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		scanf("%d", a + i);
	
	update(1e6);
	update(a[1]);
	
	int x = 1e6;
	for (int i = 2; i <= n; i++){
		
		if(a[i] >= a[i - 1] && a[i] <= x)
			update(a[i]);
		
		else{
			int l = a[i], r = 1e6, m;
			while(r > l){
				m = (l + r) >> 1;
				if(get(m) > get(a[i]))
					r = m;
				else
					l = m + 1;
			}
			x = l;
			update(a[i]);
			++ans;
		}
	}
	printf("%d", ans);
}

Compilation message (stderr)

money.cpp: In function 'int main()':
money.cpp:34:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
money.cpp:36:8: 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