Submission #818536

#	Time	Username	Problem	Language	Result	Execution time	Memory
818536		enerelt14	Measures (CEOI22_measures)	C++14	100 / 100	417 ms	41112 KiB

Main

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <climits>
#include <cmath>
#include <complex>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <vector>
using namespace std;

#define ff first
#define ss second
#define ll long long

const int MX = 2e5 + 15;

int n, m, d;
int a[MX], b[MX], ord[MX];
int cur;
pair<int, int> c[MX];
set<int> s;

struct T{
	ll mn, lmn, rmn, sum;
	T() {
		sum = mn = lmn = rmn = 0;
	}
} tree[4 * MX];

void update(int id, int l, int r, int pos, int x) {
	if(r < pos || l > pos) return;
	if(l == r) {
		tree[id].mn = x;
		tree[id].lmn = x;
		tree[id].rmn = x;
		tree[id].sum = x;
		return;
	}
	int mid = (l + r) / 2;
	update(id * 2 + 1, l, mid, pos, x);
	update(id * 2 + 2, mid + 1, r, pos, x);
	tree[id].mn = min(min(tree[id * 2 + 1].mn, tree[id * 2 + 2].mn), tree[id * 2 + 1].rmn + tree[id * 2 + 2].lmn);
	tree[id].lmn = min(tree[id * 2 + 1].lmn, tree[id * 2 + 1].sum + tree[id * 2 + 2].lmn);
	tree[id].rmn = min(tree[id * 2 + 2].rmn, tree[id * 2 + 2].sum + tree[id * 2 + 1].rmn);
	tree[id].sum = tree[id * 2 + 1].sum + tree[id * 2 + 2].sum;
}

void go() {
	for(int j = 0; j < m; j++) {
		int ind = -1;
		for(int i = 0; i < n; i++) {
			if(a[i] > b[j]) {
				ind = i;
				break;
			}
		}
		if(ind == -1) ind = n;
		for(int i = n; i > ind; i--) a[i] = a[i - 1];
		a[ind] = b[j];
		n++;
		ll mx = 0, mn = 1e18, cur = 0;
		for(int i = 0; i < n - 1; i++) {
			cur += a[i + 1] - a[i] - d;
			mn = min(mn, cur - mx);
			mx = max(mx, cur);
		}
		if(mn > 0) cout << "0\n";
		else{
			cout << -mn / 2;
			if(mn % 2)cout << ".5\n";
			else cout << "\n";
		}
	}
}

int main() {
	cin >> n >> m >> d;
	for(int i = 0; i < n; i++) cin >> a[i];
	for(int i = 0; i < m; i++) {
		cin >> b[i];
		c[i] = {b[i], i};
	}
	sort(a, a + n);
	if(n != 0) {
		go();
		return 0;
	}
	sort(c, c + m);
	for(int i = 0; i < m; i++) ord[c[i].ss] = i;
	for(int i = 0; i < m; i++) {
		auto it = s.lower_bound(ord[i]);
		if(it != s.begin()) {
			it--;
			update(0, 0, m - 1, ord[i], b[i] - c[*it].ff - d);
			it++;
		}
		if(it != s.end()) {
			update(0, 0, m - 1, *it, c[*it].ff - b[i] - d);
		}
		s.insert(ord[i]);
		if(tree[0].mn > 0) cout << "0 ";
		else{
			cout << -tree[0].mn / 2;
			if(tree[0].mn % 2) cout << ".5 ";
			else cout << " ";
		}
	}
}

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