Submission #1241699

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241699		ByeWorld	Nile (IOI24_nile)	C++20	100 / 100	147 ms	25016 KiB

nile

#include "nile.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define ll long long
#define lf ((id<<1))
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
using namespace std;
typedef pair<ll,ll> pii;
const ll MAXN = 1e5+10;
const ll INF = 2e9+10;
void chmn(auto &a, auto b){ a = min(a, b); }

ll n, q, w[MAXN], a[MAXN], b[MAXN];
ll val[MAXN];

struct seg {
	ll st[4*MAXN];
	void bd(ll id, ll l, ll r){
		st[id] = INF;
		if(l==r) return;
		
		bd(lf,l,md); bd(rg,md+1,r);
	}
	ll que(ll id, ll l, ll r,ll x, ll y){
		if(x<=l && r<=y) return st[id];
		if(r<x || y<l) return INF;
		return min(que(lf,l,md,x,y), que(rg,md+1,r,x,y));
	}
	ll upd(ll id, ll l, ll r,ll x, ll p){
		if(l==r && l==x) return st[id] = p;
		if(r<x || x<l) return st[id];
		return st[id] = min(upd(lf,l,md,x,p), upd(rg,md+1,r,x,p));
	}
} A, ODD, EV;
vector<ll> ANS;
ll ans[MAXN];

struct dsu {
	ll par[MAXN];
	void bd(){
		for(ll i=1; i<=n; i++) par[i] = i;
	}
	ll f(ll x){
		return (par[x]==x ? x : par[x]=f(par[x]));
	}
	void mer(ll x, ll y){ // x->y
		x = f(x); y = f(y);
		par[x] = y;
	}
} LE, RI;

ll calc(ll l, ll r){
	if((r-l+1)%2 == 0) return 0ll;
	ll mn = min(val[l], val[r]);
	if(r%2 == 1) chmn(mn, ODD.que(1,1,n,l,r));
	else chmn(mn, EV.que(1,1,n,l,r));
	if(l+1 <= r-1) chmn(mn, A.que(1,1,n,l+1,r-1));
	return mn; // min dari tengah sm ujung 
}
vector<pii> edge, two;
std::vector<long long> calculate_costs(std::vector<int> W, std::vector<int> aa,
                                       std::vector<int> B, std::vector<int> E) {
  	q = (ll)E.size();
  	n = W.size();
  	vector<array<ll,3>> vec;
  	for(ll i=0; i<n; i++)
  		vec.pb({W[i], aa[i], B[i]});
  	sort(vec.begin(), vec.end());

  	ll ALL = 0, mn = 0;
  	ODD.bd(1,1,n); EV.bd(1,1,n);
  	for(ll i=1; i<=n; i++){
  		w[i] = vec[i-1][0], a[i] = vec[i-1][1], b[i] = vec[i-1][2];
  		val[i] = a[i]-b[i]; // kalo sendiri
  		if(i%2) ODD.upd(1,1,n,i,val[i]);
  		else EV.upd(1,1,n,i,val[i]);
  		mn += val[i];
  		ALL += b[i];
  	}
  	for(ll i=1; i+1<=n; i++)
  		edge.pb({w[i+1]-w[i], i});
  	for(ll i=1; i+2<=n; i++){
  		two.pb({w[i+2]-w[i], i});
  		// cout << w[i+2]-w[i] << ' ' << i << " i\n";
  	}
  	sort(edge.begin(), edge.end());
  	sort(two.begin(), two.end());

  	vector<pii> que;
  	for(ll i=1; i<=q; i++) que.pb({E[i-1], i});
  	sort(que.begin(), que.end());

  	A.bd(1,1,n); LE.bd(); RI.bd();
  	ll e=0, t=0; // yg blm diupdate

	for(auto [dis, idx] : que){
		while(e<edge.size() && edge[e].fi <= dis){
			ll idx = edge[e].se;
			// merge idx, idx+1
			// cout <<mn << ' '<<idx <<" i\n";
			ll lef = LE.f(idx), rig = RI.f(idx+1);
			mn -= calc(lef, idx); mn -= calc(idx+1, rig);

			LE.mer(idx+1, idx); RI.mer(idx, idx+1);
			mn += calc(lef, rig);

			e++;
		}
		while(t<two.size() && two[t].fi <= dis){
			ll idx = two[t].se;
			// update idx+1
			// cout << mn << ' ' << idx+1 << " idx\n";
			ll lef = LE.f(idx+1), rig = RI.f(idx+1);
			mn -= calc(lef, rig);

			A.upd(1,1,n,idx+1,val[idx+1]);
			mn += calc(lef, rig);

			t++;
		}
		// l sampe r, kalo odd -> buang yg paling minimum di A
		ans[idx] = ALL+mn;
	}
	for(ll i=1; 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