Submission #173461

#	Time	Username	Problem	Language	Result	Execution time	Memory
173461		Gurban	Money (IZhO17_money)	C++14	100 / 100	696 ms	19516 KiB

money

#include <bits/stdc++.h>

#define pb push_back
#define ss second
#define ff first
#define N 1000006
#define inf 1000000009
#define ll long long
#define mid(a,b) (a+b)/2
#define pii pair<int,int>

using namespace std;
int n,a[N],T[N * 4],sm,k;

int tap(int a,int b,int l,int r,int nd){
	if(l >= a and r <= b)
		return T[nd];
	if(l > b or r < a)
		return 0;
	int cep = tap(a,b,l,mid(l,r),nd * 2);
	int sag = tap(a,b,mid(l,r) + 1,r,nd * 2 + 1);
	
	return cep + sag;
}

void upd(int pos,int l,int r,int nd){
	if(l == r){
		T[nd] = 1;
		return;
	}
	if(pos <= mid(l,r))
		upd(pos,l,mid(l,r),nd * 2);
	else upd(pos,mid(l,r) + 1,r,nd * 2 + 1);
	
	T[nd] = T[nd * 2] + T[nd * 2 + 1];
}

int main()
{
	scanf("%d",&n);
	for(int i = 1;i <= n;i++)
		scanf("%d",a + i);
	
	for(int i = 1;i <= n;){
		sm++;
		upd(a[i],1,N,1);
		for(k = i + 1;k <= n and ((a[k] == a[k - 1]) or (a[k] > a[k - 1] and tap(a[i] + 1,a[k] - 1,1,N,1) == 0));k++);
		for(int j = i + 1;j < k and j <= n;j++) upd(a[j],1,N,1);
		i = k;
	}
	printf("%d",sm);
}

Compilation message (stderr)

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