oj.uz

Submission #1066035

# Submission time Handle Problem Language Result Execution time Memory
1066035 2024-08-19T14:18:15 Z amdatta Global Warming (NOI13_gw) C++14
23 / 40
 387 ms 25512 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 = posit;

		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 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 2140 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 53 ms 2740 KB Output is correct
2 Correct 39 ms 2652 KB Output is correct
3 Correct 32 ms 2744 KB Output is correct
4 Correct 42 ms 2640 KB Output is correct
5 Correct 50 ms 2644 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 377 ms 25512 KB Output is correct
2 Correct 374 ms 25424 KB Output is correct
3 Correct 352 ms 25424 KB Output is correct
4 Correct 344 ms 25428 KB Output is correct
5 Correct 351 ms 24656 KB Output is correct

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 350 ms 24872 KB Output is correct
2 Correct 363 ms 24656 KB Output is correct
3 Correct 387 ms 24660 KB Output is correct
4 Incorrect 256 ms 18984 KB Output isn't correct
5 Halted 0 ms 0 KB -