oj.uz

Submission #1065939

# Submission time Handle Problem Language Result Execution time Memory
1065939 2024-08-19T13:19:36 Z amdatta Global Warming (NOI13_gw) C++14
23 / 40
 409 ms 25536 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;
	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++;
		}

		ans = max(ans, i - merges + 1);
		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 352 KB Output is correct
4 Correct 1 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 31 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 33 ms 2840 KB Output is correct
2 Correct 39 ms 2388 KB Output is correct
3 Correct 34 ms 2644 KB Output is correct
4 Correct 35 ms 2840 KB Output is correct
5 Correct 37 ms 2752 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 385 ms 25428 KB Output is correct
2 Correct 338 ms 25520 KB Output is correct
3 Correct 359 ms 25408 KB Output is correct
4 Correct 378 ms 25536 KB Output is correct
5 Correct 352 ms 24880 KB Output is correct

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 409 ms 24880 KB Output is correct
2 Correct 347 ms 24660 KB Output is correct
3 Correct 396 ms 24884 KB Output is correct
4 Incorrect 227 ms 19008 KB Output isn't correct
5 Halted 0 ms 0 KB -