Submission #762576

#	Time	Username	Problem	Language	Result	Execution time	Memory
762576		KN200711	Baloni (COCI15_baloni)	C++14	100 / 100	938 ms	96764 KiB

baloni

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

int arr[1000001];
bool vis[1000001];

set<int> pos[1000001];

int main() {
	int N;
	scanf("%d", &N);
	
//	for(int i=0;i<=1e6;i++) pos[i].clear();
	
	for(int i=1;i<=N;i++) {
		scanf("%d", &arr[i]);
		pos[arr[i]].insert(i);
		vis[i] = 0;
	}
	int ans = 0;
	for(int i=1;i<=N;i++) {
	//	cout<<"i : "<<i<<endl;
		if(vis[i]) continue;
	//	cout<<"ii : "<<i<<endl;
		
		int K = i + 1, H = arr[i] - 1;
		vis[i] = 1;
		ans++;
		while(H > 0 && pos[H].size()) {
		//	cout<<"H, K : "<<H<<" "<<K<<endl;
			auto p = pos[H].lower_bound(K);
		//	if(p == pos[H].end()) cout<<"end"<<endl;
			if(p == pos[H].end()) break;
		//	cout<<"vis"<<endl;
		//	cout<<"p : "<<*p<<endl;
			vis[*p] = 1;
			K =  *p + 1;
			
			pos[H].erase(p);
			H--;
		}
	//	cout<<endl;
	//	pos[H].insert(0);
	//	cout<<"aft : "<<H<<" "<<K<<" "<<pos[H].size()<<" "<<endl;
	//	cout<<endl;
	}
	printf("%d\n", ans);
	return 0;
}

Compilation message (stderr)

baloni.cpp: In function 'int main()':
baloni.cpp:11:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
baloni.cpp:16:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |   scanf("%d", &arr[i]);
      |   ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 100 / 100