Submission #869233

#	Time	Username	Problem	Language	Result	Execution time	Memory
869233		Hakiers	Measures (CEOI22_measures)	C++17	0 / 100	218 ms	62556 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
constexpr int BASE = 1 << 19;
constexpr ld oo = 1e18;
struct Node{
	ld l, r, res;
};
vector<pair<int, int>> Queries;
Node TREE[BASE << 1];
pair<int, ld> pos[BASE];
int n, m;
ld D;

void przypisz(){
	int id = 0;
	for(int i = 1; i <= n+m; i++){
		auto [val, idx] = Queries[i-1];
		pos[idx] = {id++, val};
	}
}

Node merge(Node l, Node r){
	if(r.r == oo)
		return l;
	else if(l.r == oo)
		return r;
	
	Node out;
	if(l.res > r.res){
		ld delta = min((l.res - r.res), max((l.r + D) - r.l, (ld)0));
		r.l += delta;
		r.r += delta;
		out.res = l.res;
	}
	else{
		ld delta = min((r.res - l.res), max((l.r + D) - r.l, (ld)0));
		l.l -= delta;
		l.r -= delta;
		out.res = r.res;
	}
	
	ld delta = max((ld)0, (l.r + D - r.l));
	delta /=2;
	out.res += delta;
	out.l = l.r - delta;
	out.r = r.r + delta;
	
	return out;
}


void update(int v, ld val){
	v += BASE;
	TREE[v].res = 0;
	TREE[v].l = TREE[v].r = val;
	v/=2;
	
	while(v > 0){
		int l = 2*v, r = 2*v+1;
		TREE[v] = merge(TREE[l], TREE[r]);
		v/=2;
	}
}


void treeinit(){
	for(int i = 0; i < (BASE << 1); i++)
		TREE[i].l = TREE[i].r = oo;
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m >> D;
	treeinit();
	for(int i = 1; i <= n; i++){
		int a;
		cin >> a;
		Queries.push_back({a, i});
	}
	
	for(int i = n+1; i <= n+m; i++){
		int a;
		cin >> a;
		Queries.push_back({a, i});
	}
	
	sort(Queries.begin(), Queries.end());
	przypisz();
	
	for(int i = 1; i <= n; i++)
		update(pos[i].first, pos[i].second);
	
	for(int i = n+1; i <= m+n; i++){
		update(pos[i].first, pos[i].second);
		cout << TREE[1].res << " ";
	}
	cout << "\n";

}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 14
• Subtask 3: 0 / 35
• Subtask 4: 0 / 41