Submission #1065939

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065939		amdatta	Global Warming (NOI13_gw)	C++14	23 / 40	409 ms	25536 KiB

gw

#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 / 6
• Subtask 2: 0 / 6
• Subtask 3: 7 / 7
• Subtask 4: 10 / 10
• Subtask 5: 0 / 11