Submission #762561

#	Time	Username	Problem	Language	Result	Execution time	Memory
762561		KN200711	Baloni (COCI15_baloni)	C++14	0 / 100	471 ms	131072 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=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++) {
		if(vis[i]) continue;
		int K = i + 1, H = arr[i] - 1;
		vis[i] = 1;
		ans++;
		while(H) {
		//	cout<<H<<endl;
			auto p = pos[H].lower_bound(K);
			if(p == pos[H].end()) break;
		//	cout<<"vis"<<endl;
			vis[*p] = 1;
			K =  *p + 1;
			H--;
			pos[H].erase(p);
		}
	}
	printf("%d\n", ans);
}

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:14:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |   scanf("%d", &arr[i]);
      |   ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 0 / 100