제출 #691490

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
691490		Sohsoh84	Measures (CEOI22_measures)	C++17	100 / 100	431 ms	83604 KiB

Main

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

#define all(x)			(x).begin(),(x).end()
#define X			first
#define Y			second
#define sep			' '
#define endl			'\n'
#define debug(x)		cerr << #x << ": " <<  x << endl;

const ll MAXN = 4e6 + 10;
const ll INF = 1e18;
const pll SG_D = {INF, -INF};

ll n, m, d, ans, lz[MAXN];
pll sg[MAXN];
vector<pll> X, Q;

namespace fenwick {
	int fen[MAXN];

	inline void update(int ind, int val) {
		for (++ind; ind < MAXN; ind += ind & -ind)
			fen[ind] += val;
	}

	inline int query(int ind) {
		int ans = 1;
		for (++ind; ind > 0; ind -= ind & -ind)
			ans += fen[ind];

		return ans;
	}
}

inline pll merge(pll a, pll b) {
	return pll(min(a.X, b.X), max(a.Y, b.Y));
}

inline void push(ll v) {
	sg[v].X += lz[v];
	sg[v].Y += lz[v];

	if ((v << 1 | 1) < MAXN) {
		lz[v << 1] += lz[v];
		lz[v << 1 | 1] += lz[v];
	}

	lz[v] = 0;
}

void point_set(int ind, ll val, int l = 1, int r = n, int v = 1) {
	push(v);
	if (l == r) sg[v] = {val, val};
	else {
		int mid = (l + r) >> 1;
		if (ind <= mid) point_set(ind, val, l, mid, v << 1), push(v << 1 | 1);
		else point_set(ind, val, mid + 1, r, v << 1 | 1), push(v << 1);

		sg[v] = merge(sg[v << 1], sg[v << 1 | 1]);
	}
}

void update(int ql, int qr, ll val, int l = 1, int r = n, int v = 1) {
	push(v);
	if (ql > r || qr < l) return;
	if (ql <= l && qr >= r) {
		lz[v] += val;
		push(v);
		return;
	}

	int mid = (l + r) >> 1;
	update(ql, qr, val, l, mid, v << 1);
	update(ql, qr, val, mid + 1, r, v << 1 | 1);
	sg[v] = merge(sg[v << 1], sg[v << 1 | 1]);
}

pll query(int ql, int qr, int l = 1, int r = n, int v = 1) {
	push(v);
	if (ql > r || qr < l) return SG_D;
	if (ql <= l && qr >= r) return sg[v];

	int mid = (l + r) >> 1;
	return merge(query(ql, qr, l, mid, v << 1),
			query(ql, qr, mid + 1, r, v << 1 | 1));
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> m >> d;
	n += m;
	for (int i = 1; i <= n; i++) {
		int x;
		cin >> x;
		X.push_back({x, i});
		Q.push_back({i, x});
	}

	fill(sg, sg + MAXN, SG_D);

	sort(all(X));
	for (pll e : Q) {
		auto [i, x] = e;
		auto ind = lower_bound(all(X), pll(x, i)) - X.begin() + 1;

		int f_ind = fenwick::query(ind);
		fenwick::update(ind, 1);

		ll f = d * f_ind - x;

		point_set(ind, f);
		if (ind < n) update(ind + 1, n, d);
		ans = max(ans, query(ind, n).Y - query(1, ind).X);
		
		if (i > n - m) {
			cout << ans / 2;
			if (ans % 2) cout << ".5";
			cout << endl;
		}
	}
	return 0;
}

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