Submission #1102164

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102164		peacebringer1667	Nile (IOI24_nile)	C++17	100 / 100	98 ms	21168 KiB

nile

#include "nile.h"
#include<bits/stdc++.h>
#define ll long long
#define ldb long double
#define fi first
#define se second
#define sza(a) (int)a.size()
#define pir pair<int,int>
#define pirll pair<ll,ll>
using namespace std;
const int maxn = 1e5 + 5;
const int inf = 2e9;

struct CTDL{
	int u = 0,v = 0,dist = 0;
	bool operator <(const CTDL&other) const{
		return (dist < other.dist);
	}
}; 

struct segment_tree{
	int seg[4*maxn];
	
	void init(int l,int r,int v){
		seg[v] = inf;
		
		if (l == r) return;
		int w = (l + r)/2;
		init(l,w,2*v + 1);
		init(w + 1,r,2*v + 2);
	}
	
	void update(int l,int r,int v,int p,int val){
		if (l > p || r < p) return;
		if (l == r){
			seg[v] = min(seg[v],val);
			return;
		}
		
		int w = (l + r)/2;
		update(l,w,2*v + 1,p,val);
		update(w + 1,r,2*v + 2,p,val);
		seg[v] = min(seg[2*v + 1],seg[2*v + 2]);
	}
	
	int calc(int l,int r,int v,int lx,int rx){
		if (l > rx || r < lx) return inf;
		if (l >= lx && r <= rx) return seg[v];
		
		int w = (l + r)/2;
		return min(calc(l,w,2*v + 1,lx,rx),calc(w + 1,r,2*v + 2,lx,rx));
	}
} seg[2];

vector <CTDL> lst,skip_list;
int a[maxn],W[maxn],A[maxn],B[maxn];
pir Q[maxn],arr[maxn];


struct DSU{
	int par[maxn],M[maxn][2],L[maxn],R[maxn],sz[maxn];
	ll sum[maxn],cost[maxn];
	
	int findp(int x){
		return (x == par[x]) ? x : par[x] = findp(par[x]);
	}
	
	void init(int n){
		for (int i = 1 ; i <= n ; i++){
			sum[i] = a[i];
			sz[i] = 1;
			M[i][i % 2] = abs(a[i]);
			M[i][(i % 2) ^ 1] = INT_MAX;
			
			L[i] = i;
			R[i] = i;
			par[i] = i;
			
			cost[i] = 0;
		}
	}
	
	ll add(int u,int v,int n){
		int x = findp(u),y = findp(v);
		if (x != y){
			ll res = sum[x] + sum[y];
			ll tmp = cost[x] + cost[y];
			
			sz[x] += sz[y];
			sum[x] += sum[y];
			
			M[x][0] = min(M[x][0],M[y][0]);
			M[x][1] = min(M[x][1],M[y][1]);
			
			L[x] = min(L[x],L[y]);
			R[x] = max(R[x],R[y]);
			
			par[y] = x;
			
			if (sz[x] % 2){
			  res += M[x][L[x] % 2];
		      
		      int id = 1 - (L[x] % 2);
		      res = min(res,sum[x] + (ll)seg[id].calc(1,n,0,L[x],R[x]));
			}
		
			cost[x] = res;
			return res - tmp;
		}
		
		return 0;
	}
	
	ll recalc(int u,int n){
		int x = findp(u);
		
		ll tmp = cost[x];
		ll res = cost[x];
		
		if (sz[x] % 2 && sz[x] > 1){
			int id = (L[x] % 2) ^ 1;
		    res = min(res,sum[x] + (ll)seg[id].calc(1,n,0,L[x],R[x]));
		}
		cost[x] = res;
		return res - tmp;
	}
	
} dsu;

void prepare(vector <int> W,vector <int> A,vector <int> B,vector <int> E){
	int n = W.size();
	int q = E.size();
	
	lst.clear();
	skip_list.clear();
	
	seg[0].init(1,n,0);
	seg[1].init(1,n,0);
	
	//
	for (int i = 1 ; i <= n ; i++) arr[i] = {W[i - 1],B[i - 1] - A[i - 1]};
	sort(arr + 1,arr + 1 + n);
	
	for (int i = 1 ; i <= n ; i++)
	  a[i] = arr[i].se;
	
	for (int i = 1 ; i <= q ; i++)
		Q[i] = {E[i - 1],i};
	sort(Q + 1,Q + 1 + q);
	//////
	
	//////// connected components
	for (int i = 1 ; i < n ; i++){
	  lst.push_back({i,i + 1,arr[i + 1].fi - arr[i].fi});
      if (i + 2 <= n)
        skip_list.push_back({i + 1,i + 1,arr[i + 2].fi - arr[i].fi});
	}
	
	sort(skip_list.begin(),skip_list.end());
	sort(lst.begin(),lst.end());
	
	dsu.init(n);
	///////
}

vector <ll> calculate_costs(vector <int> W,vector <int> A,vector <int> B,vector <int> E){
	vector <ll> res;
	int n = W.size(),q = E.size();
	res.resize(q);
	prepare(W,A,B,E);
	
	ll cur = 0;
	for (int x : A) cur += x;
	
	int p = 0,p_skip = 0;
	for (int i = 1 ; i <= q ; i++){
		int D = Q[i].fi,id = Q[i].se;
		
		while (p_skip < skip_list.size() && skip_list[p_skip].dist <= D){
			int u = skip_list[p_skip].u;
			seg[u % 2].update(1,n,0,u,abs(a[u]));
			
			cur += dsu.recalc(u,n);
			
			p_skip++;
		}
		
		while (p < lst.size() && lst[p].dist <= D){
			cur += dsu.add(lst[p].u,lst[p].v,n);
			p++;
		}
		
		res[id - 1] = cur;
	}
	
	return res;
}

Compilation message (stderr)

nile.cpp: In function 'std::vector<long long int> calculate_costs(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
nile.cpp:179:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<CTDL>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  179 |   while (p_skip < skip_list.size() && skip_list[p_skip].dist <= D){
      |          ~~~~~~~^~~~~~~~~~~~~~~~~~
nile.cpp:188:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<CTDL>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  188 |   while (p < lst.size() && lst[p].dist <= D){
      |          ~~^~~~~~~~~~~~

• 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