oj.uz

Submission #1065948

# Submission time Handle Problem Language Result Execution time Memory
1065948 2024-08-19T13:27:37 Z amdatta Global Warming (NOI13_gw) C++14
34 / 40
 341 ms 25528 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 == lastElement){
			numElementsEqual++;
		}else{
			numElementsEqual = 0;
		}

		lastElement = pos[i].first;

		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 0 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 20 ms 2144 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 37 ms 2608 KB Output is correct
2 Correct 22 ms 2652 KB Output is correct
3 Correct 33 ms 2640 KB Output is correct
4 Correct 29 ms 2652 KB Output is correct
5 Correct 28 ms 2628 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 341 ms 25380 KB Output is correct
2 Correct 331 ms 25528 KB Output is correct
3 Correct 339 ms 25436 KB Output is correct
4 Correct 331 ms 25428 KB Output is correct
5 Correct 325 ms 24660 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 328 ms 24660 KB Output is correct
2 Correct 331 ms 24872 KB Output is correct
3 Correct 339 ms 24656 KB Output is correct
4 Correct 216 ms 19028 KB Output is correct
5 Correct 216 ms 19028 KB Output is correct