Submission #1197801

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197801		ansori	Nile (IOI24_nile)	C++20	100 / 100	437 ms	37808 KiB

nile

#include "nile.h"
#include<bits/stdc++.h>
#define ll long long
#define fi first 
#define se second
using namespace std;
const int inf = 1e9 , N = 1e5 + 5;
vector<ll> sb(N);
ll sans;
int s;
vector<vector<int>> t(N * 4 , vector<int> (4 , inf));
vector<int> kur;
set<pair<int , pair<int , ll>>> st;
vector<int> mrg(vector<int> a, vector<int> b){
	return {min(a[0] , b[0]) , min(a[1] , b[1]) , min(a[2] , b[2]) , min(a[3] , b[3])};
}
void update(int v , int l , int r , int j , int x , int tp){
	if(r - l == 1){
		if(tp == 1) t[v][l % 2] = x;
		else t[v][l % 2 + 2] = x;
	}
	else{
		int m = (l + r) / 2;
		if(j < m) update(v * 2 , l , m , j , x , tp);
		else update(v * 2 + 1 , m , r , j , x , tp);
		t[v] = mrg(t[v * 2] , t[v * 2 + 1]);
	}
}
void gett(int v , int l , int r , int l1 , int r1){
	if(l <= l1 and r >= r1){
		kur = mrg(kur , t[v]);
	}
	else{
        int m = (l1 + r1) / 2;
        if(!(l1 >= r || m <= l)) {
            gett(v * 2 , l , r , l1 , m);
        }
        if(!(m >= r || r1 <= l)) {
            gett(v * 2 + 1 , l , r , m , r1);
        }
	}
}
vector<int> get(int l , int r){
	kur = {inf , inf , inf , inf};
	gett(1 , l , r + 1 , 0 , s);
	return kur;
}
void updt(int j , int x , int tp){
	update(1 , 0 , s , j , x , tp);
}
void upd(int p){
	auto to = (-- st.lower_bound({p + 1 , {-1 , -1}}));
	int l = to -> fi;
	int r = (to -> se).fi;
	ll sm = (to -> se).se;
	ll ons = sb[r];
	if(l) ons -= sb[l - 1];
	sans -= sm;
	if((r - l + 1) % 2 == 1){
		vector<int> ff = get(l , r);
		//cout << l << ' ' << r << ' ' << ff[2 + ((l + 1) % 2)] << ' ';
		ons += min(ff[l % 2] , ff[2 + ((l + 1) % 2)]);
	}
	st.erase(to);
	st.insert({l , {r , ons}});
	sans += (to -> se).se;	
}
void unit(int p){
	auto to = (st.lower_bound({p + 1 , {-1 , -1}}));
	int l1 = p + 1;
	int r1 = (to -> se).fi;
	ll sm1 = (to -> se).se;
	to --;
	int l0 = to -> fi;
	int r0 = p;
	ll sm0 = (to -> se).se;
	st.erase({l1 , {r1 , sm1}});
	st.erase({l0 , {r0 , sm0}});
	sans -= (sm1 + sm0);
	st.insert({l0 , {r1 , 0}});
	upd(l0);
}
std::vector<long long> calculate_costs(std::vector<int> w, std::vector<int> a, std::vector<int> b, std::vector<int> e) {
	int q = e.size();
	int n = w.size();
	s = 1;
	while(s < n) s *= 2;
	vector<pair<int , int>> p(n);
	for(int i = 0;i < n; ++ i) p[i] = {w[i] , i};
	sort(p.begin() , p.end());
	vector<pair<int , pair<int , int>>> ivent;
	// time , type ivent , position
	for(int i = 1;i < n; ++ i){
		ivent.push_back({p[i].fi - p[i - 1].fi , {1 , i - 1}});
		if(i > 1) ivent.push_back({p[i].fi - p[i - 2].fi , {2 , i - 1}});
	}
	vector<ll> ans(q);
	for(int i = 0;i < q; ++ i) ivent.push_back({e[i] , {3 , i}});
	sort(ivent.begin() , ivent.end());
	sb[0] = b[p[0].se];
	for(int i = 0;i < n; ++ i){
		sans += a[i];
		st.insert({i , {i , a[p[i].se]}});
		if(i) sb[i] = sb[i - 1] + b[p[i].se];
		updt(i , a[p[i].se] - b[p[i].se] , 1);
	}
	for(auto to : ivent){
		int dst = to.fi , t = to.se.fi , pos = to.se.se;
		if(t == 3) ans[pos] = sans;
		else if(t == 1){
			unit(pos);
		}
		else{
			updt(pos , a[p[pos].se] - b[p[pos].se] , 2);
			upd(pos);
		}
		//cout << dst << ' ' << t << ' ' << pos << ' ' << sans << '\n';
	}
	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