Submission #1221925

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221925		Dan4Life	Nile (IOI24_nile)	C++20	100 / 100	78 ms	13628 KiB

nile

#include "nile.h"
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define sz(a) (int)a.size()
#define all(a) begin(a),end(a)

using ll = long long;
using ar2 = array<int,2>;
using ar3 = array<int,3>;
using vi = vector<int>;
using vll = vector<ll>;

const int mxN = (int)1e5+10;
const int INF = (int)1e9+10;
const ll LINF = (ll)1e18+10;

int n, q;
vi v, a, b;
ll ANS[mxN];
bitset<mxN> activated;

template<int SZ>
struct DSU{
	int p[SZ], sz[SZ], fi[SZ], la[SZ];
	ll mn[SZ][2], best[SZ], ans;
	ll active[SZ];
	
	void init(int n=SZ){
		ans = 0;
		for(int i = 0; i < n; i++){
			p[i] = fi[i] = la[i] = i, sz[i] = 1;
			mn[i][0]=best[i]=a[v[i]];
			mn[i][1]=active[i]=LINF;
			ans+=best[i]; 	
		}
	}
	
	int findSet(int i){
		return i==p[i]?i:p[i]=findSet(p[i]);
	}
	
	bool isSameSet(int i, int j){
		return findSet(i)==findSet(j);
	}
	
	void unionSet(int i, int j){
		if(i>j) swap(i,j);
		int x = findSet(i), y = findSet(j);
		if(x==y) return;
		
		if(sz[x]%2) ans-=best[x];
		if(sz[y]%2) ans-=best[y];
		
		mn[x][0] = min(mn[x][0], mn[y][sz[x]%2]);
		mn[x][1] = min(mn[x][1], mn[y][sz[x]%2==0]);
		active[x] = min(active[x], active[y]);
		
		vi ind; ind.clear();
		if(activated[la[x]]) ind.pb(la[x]);
		if(activated[fi[y]]) ind.pb(fi[y]);
		
		p[y] = x, sz[x]+=sz[y];
		fi[x] = min(fi[x], fi[y]);
		la[x] = max(la[x], la[y]);
		
		for(auto k : ind) activate(k,0);
		best[x] = min(active[x], mn[x][0]);
		if(sz[x]%2) ans+=best[x];
	}
	
	void activate(int i, bool ok=1){
		activated[i] = 1;
		int x = findSet(i);
		if(i!=fi[x] and i!=la[x])
			active[x] = min(active[x], (ll)a[v[i]]);
		if(ok and sz[x]%2) ans-=best[x];
		best[x] = min(best[x], active[x]);
		if(ok and sz[x]%2) ans+=best[x];
	}
};

DSU<mxN> dsu;

vll calculate_costs(vi W, vi A, vi B, vi E){
	a = A, b = B; n = sz(W); q = sz(E); activated.reset();
	for(int i = 0; i < n; i++) a[i]-=b[i];
	
	v.resize(n,0); iota(all(v),0);
	sort(all(v),[&](int i, int j){ return W[i]<W[j]; });
	
	vi Q(q,0); iota(all(Q),0);
	sort(all(Q),[&](int i, int j){ return E[i]<E[j]; });
	
	vector<ar2> dis; dis.clear();
	for(int i = 0; i < n-1; i++) 
		dis.pb({W[v[i+1]]-W[v[i]], i});
	sort(all(dis)); 
	
	vector<ar2> active; active.clear();
	for(int i = 1; i < n-1; i++) 
		active.pb({W[v[i+1]]-W[v[i-1]], i});
	sort(all(active)); 

	ll tot = accumulate(all(b),0ll); 
	int j=0, k=0; dsu.init(n);
	for(auto i : Q){
		while(k<sz(active) and active[k][0]<=E[i])
			dsu.activate(active[k][1]), k++;
		while(j<sz(dis) and dis[j][0]<=E[i])
			dsu.unionSet(dis[j][1],dis[j][1]+1), j++;
		ANS[i] = dsu.ans+tot;
	}
	
	vll ans; ans.clear();
	for(int i = 0; i < q; i++) ans.pb(ANS[i]);
	return ans;
}

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