Submission #1177037

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177037		Kaztaev_Alisher	Nile (IOI24_nile)	C++20	100 / 100	165 ms	60792 KiB

nile

#include <bits/stdc++.h>

#define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
#define all(a) a.begin() , a.end()
#define F first
#define S second

using namespace std;
using ll = long long;

const ll N = 2e5+5 , inf = 2e9 + 7;
const ll INF = 1e18 ,   mod = 1e9+7;

ll w[N] , a[N] , b[N] , ord[N] , d[N] , n , q;
ll p[N] , sz[N] , cur[N][2] , mn[N] , mx[N] , c[N];
ll res , sp[N][20][2] , lg[N];
ll get(ll x){
	if(p[x] == x) return x;
	return p[x] = get(p[x]);
}
ll getmn(ll l , ll r , ll k){
	ll len = lg[r-l+1];
	return min(sp[l][len][k] , sp[r-(1 << len)+1][len][k]);
}
void merge(ll a, ll b){
	a = get(a);
	b = get(b);
	if(sz[b] % 2) res -= min(getmn(mn[b],mx[b],b%2) , cur[b][1-b%2]);
	if(sz[a] % 2) res -= min(getmn(mn[a],mx[a],a%2) , cur[a][1-a%2]);
	mn[a] = min(mn[a] , mn[b]);
	mx[a] = max(mx[a] , mx[b]);
	cur[a][a%2] = min(cur[a][a%2] , cur[b][a%2]);
	cur[a][1-a%2] = min(cur[a][1-a%2] , cur[b][1-a%2]);
	sz[a] += sz[b];
	p[b] = a;
	if(sz[a] % 2) res += min(getmn(mn[a],mx[a],a%2) , cur[a][1-a%2]);
}
void tryy(ll x){
	ll par = get(x);
	ll l = mn[par] , r = mx[par];
	if(sz[par] % 2) res -= min(getmn(mn[par],mx[par],par%2) , cur[par][1-par%2]);
	if(x-1 >= l && x+1 <= r){
		cur[par][x%2] = min(cur[par][x%2] , c[x]);
	}
	if(sz[par] % 2) res += min(getmn(mn[par],mx[par],par%2) , cur[par][1-par%2]);
}
ll w1[N] , a1[N] , b1[N];
void gosort(){
	for(ll i = 1; i <= n; i++){
		w1[i] = w[i];
		a1[i] = a[i];
		b1[i] = b[i];
		ord[i] = i;
	}
	sort(ord+1,ord+1+n,[&](ll i , ll j){
		return w[i] < w[j];
	});
	for(ll i = 1; i <= n; i++){
		w[i] = w1[ord[i]];
		a[i] = a1[ord[i]];
		b[i] = b1[ord[i]];
		c[i] = a[i]-b[i];
	}
}
vector<long long> solve(){
	vector<ll> vec(q,0);
	gosort();
	ll sum = 0;
	for(ll i = 1; i <= n; i++){
		lg[i] = lg[i/2]+1;
		if(i == 1) lg[i] = 0;
		sp[i][0][0] = sp[i][0][1] = INF;
		sp[i][0][i%2] = c[i];
		sum += b[i];
		res += c[i];
		p[i] = i; sz[i] = 1;
		mn[i] = i; mx[i] = i;
		cur[i][0] = cur[i][1] = INF;
	}
	for(int j = 1; j <= lg[n]; j++){
		for(int i = 1; i+(1 << j)-1 <= n; i++){
			sp[i][j][0] = min(sp[i][j-1][0] , sp[i+(1 << (j-1))][j-1][0]);
			sp[i][j][1] = min(sp[i][j-1][1] , sp[i+(1 << (j-1))][j-1][1]);
		}
	}
	for(ll i = 1; i <= q; i++) ord[i] = i;
	sort(ord+1,ord+1+q,[&](ll i , ll j){
		return d[i] < d[j];
	});
	sort(p+1,p+1+q);
	multiset<pair<ll,ll>> st , st2;
	for(ll i = 1; i+1 <= n; i++){
		st.insert({abs(w[i]-w[i+1]) , i});
		if(i-1 >= 1) st2.insert({abs(w[i-1]-w[i+1]) , i});
	}
	for(ll _ = 1; _ <= q; _++){
		ll i = ord[_];
		while(st.size() && st.begin()->F <= d[i]){
			pair<ll,ll> x = *st.begin();
			st.erase(st.find(x));
			merge(x.S,x.S+1);
		}
		while(st2.size() && st2.begin()->F <= d[i]){
			pair<ll,ll> x = *st2.begin();
			st2.erase(st2.find(x));
			// cout << sum <<" " << x.S <<" " << res << "\n";
			tryy(x.S);
		}
		vec[i-1] = sum+res;
	}
	return vec;
}
vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E){
	n = W.size();
	for(int i = 1; i <= n; i++){
		w[i] = W[i-1];
		a[i] = A[i-1];
		b[i] = B[i-1];
	}
	q = E.size();
	for(int i = 1; i <= q; i++){
		d[i] = E[i-1];
	}
	return solve();
}

// int main() {
  // int N;
  // assert(1 == scanf("%d", &N));
  // std::vector<int> W(N), A(N), B(N);
  // for (int i = 0; i < N; i++)
    // assert(3 == scanf("%d%d%d", &W[i], &A[i], &B[i]));
  // int Q;
  // assert(1 == scanf("%d", &Q));
  // std::vector<int> E(Q);
  // for (int j = 0; j < Q; j++)
    // assert(1 == scanf("%d", &E[j]));
  // fclose(stdin);
// 
  // std::vector<long long> R = calculate_costs(W, A, B, E);
// 
  // int S = (int)R.size();
  // for (int j = 0; j < S; j++)
    // printf("%lld\n", R[j]);
  // fclose(stdout);
// 
  // return 0;
// }

• 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