oj.uz

Submission #1066015

# Submission time Handle Problem Language Result Execution time Memory
1066015 2024-08-19T14:09:55 Z amdatta Global Warming (NOI13_gw) C++14
34 / 40
 360 ms 25428 KB 
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class DSU {
	private:
		vector<int> parents;
		vector<int> sizes;
	public:
		DSU(int size): parents(size), sizes(size, 1) {
			for(int i = 0; i < size; i++){
				parents[i] = i;
			}
		}

		//Path Compression
		int find(int node){
			return parents[node] == node ? node : (parents[node] = find(parents[node]));
		}

		bool merge(int x, int y){
			int x_root = find(x);
			int y_root = find(y);
			if(x_root == y_root){
				//Merge did not do anything
				return false;
			}
			//Small to Large
			if(sizes[x] > sizes[y]){
				swap(x, y);
			}
			parents[x_root] = parents[y_root];
			sizes[x_root] += sizes[y];
			return true;
		}

		bool same_set(int x, int y){
			return find(x) == find(y);
		}
};


int main(void){
	int n;
	cin >> n;
	vector<pair<int, int> > pos(n);
	vector<bool> seen(n);
	for(int i = 0; i < n; i++){
		cin >> pos[i].first;
		pos[i].second = i;
	}

	sort(pos.begin(), pos.end(), greater<pair<int, int> > ());

	DSU comps(n + 1);

	int ans = 0;
	int merges = 0;

	int lastElement = -1;
	int numElementsEqual = 0;

	for(int i = 0; i < n; i++){
		int posit = pos[i].second;
		if(posit - 1 >= 0 && seen[posit - 1]){
			comps.merge(posit - 1, posit);
			merges++;
		}
		if(posit + 1 < n && seen[posit + 1]){
			comps.merge(posit, posit + 1);
			merges++;
		}

		if(pos[i].first == pos[lastElement].first && ((i == lastElement - 1 ) || (i == lastElement + 1))){
			numElementsEqual++;
		}else{
			numElementsEqual = 0;
		}

		lastElement = i;

		ans = max(ans, i - merges + 1 - numElementsEqual);
		seen[posit] = true;
	}

	cout << ans << "\n";

	return 0;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 2256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 2836 KB Output is correct
2 Correct 21 ms 2652 KB Output is correct
3 Correct 30 ms 2648 KB Output is correct
4 Correct 30 ms 2644 KB Output is correct
5 Correct 31 ms 2644 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 337 ms 25428 KB Output is correct
2 Correct 343 ms 25428 KB Output is correct
3 Correct 333 ms 25428 KB Output is correct
4 Correct 353 ms 25428 KB Output is correct
5 Correct 319 ms 24876 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 360 ms 24916 KB Output is correct
2 Correct 327 ms 24912 KB Output is correct
3 Correct 332 ms 24736 KB Output is correct
4 Correct 214 ms 18984 KB Output is correct
5 Correct 209 ms 19024 KB Output is correct