Submission #1205991

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205991		JakobZorz	Nile (IOI24_nile)	C++20	32 / 100	84 ms	10428 KiB

nile

#include "nile.h"
#include<algorithm>
#include<iostream>
#include<map>
using namespace std;
typedef long long ll;

struct DSU{
	vector<int>par; // parent: -n ima root, kjer je n velikost, n ima pa non-root in to pove, da je n v isti komponenti
	ll cost;
	DSU(int n){
		par=vector(n,-1);
		cost=2*n;
	}
	int get(int a){
		if(par[a]<0)
			return a;
		return par[a]=get(par[a]);
	}
	int merge(int a,int b){
		a=get(a);
		b=get(b);
		if(a==b)
			return 0;
		if(par[a]>par[b])
			swap(a,b);
		cost-=get_cost(a);
		cost-=get_cost(b);
		par[a]+=par[b];
		par[b]=a;
		cost+=get_cost(a);
		return 1;
	}
	int get_cost(int a){
		int s=-par[get(a)];
		if(s%2==0)
			return s;
		else
			return s+1;
	}
};
	
vector<ll>calculate_costs(vector<int>W,vector<int>_A,vector<int>_B,vector<int>E){
	int n=(int)W.size();
	sort(W.begin(),W.end());	
	vector<int>srt=E;
	sort(srt.begin(),srt.end());	
	map<int,ll>ans;

	vector<pair<int,int>>arr; // (W[i+1]-W[i],i)
	for(int i=0;i+1<n;i++)
		arr.push_back({W[i+1]-W[i],i});
	sort(arr.begin(),arr.end());	
	reverse(arr.begin(),arr.end());	

	DSU dsu(n);
	for(int D:srt){
		while(arr.size()&&arr.back().first<=D){
			dsu.merge(arr.back().second,arr.back().second+1);		
			arr.pop_back();
		}
		ans[D]=dsu.cost;
	}

	vector<ll>res;
	for(int D:E)
		res.push_back(ans[D]);
	return res;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 6
• Subtask 2: 0 / 13
• Subtask 3: 17 / 17
• Subtask 4: 0 / 11
• Subtask 5: 0 / 20
• Subtask 6: 15 / 15
• Subtask 7: 0 / 18