oj.uz

Submission #762576

# Submission time Handle Problem Language Result Execution time Memory
762576 2023-06-21T14:04:21 Z KN200711 Baloni (COCI15_baloni) C++14
100 / 100
 938 ms 96764 KB 
# 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

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47248 KB Output is correct
2 Correct 22 ms 47328 KB Output is correct
3 Correct 23 ms 47388 KB Output is correct
4 Correct 23 ms 47548 KB Output is correct
5 Correct 809 ms 91872 KB Output is correct
6 Correct 938 ms 96764 KB Output is correct
7 Correct 625 ms 88024 KB Output is correct
8 Correct 616 ms 87516 KB Output is correct
9 Correct 732 ms 90024 KB Output is correct
10 Correct 733 ms 91516 KB Output is correct