Submission #799616

#	Time	Username	Problem	Language	Result	Execution time	Memory
799616		GusterGoose27	Measures (CEOI22_measures)	C++17	0 / 100	98 ms	32484 KiB

Main

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll inf = 1e18;

int n, m, d;

class stree {
public:
	int lp, rp;
	stree *l = nullptr;
	stree *r = nullptr;
	ll mx = -inf;
	ll mn = inf;
	ll best = -inf;
	int pos_add = 0; // applies to everything in subtree incl root
	stree(int lv, int rv) {
		lp = lv;
		rp = rv;
		if (lp < rp) {
			int mid = (lp+rp)/2;
			l = new stree(lp, mid);
			r = new stree(mid+1, rp);
		}
	}
	void reupd() {
		mx = (ll)pos_add*d+max(l->mx, r->mx);
		mn = (ll)pos_add*d+min(l->mn, r->mn);
		best = max(mx-mn, max(l->best, r->best));
	}
	void set_val(int p, ll v) {
		if (lp > p || rp < p) return;
		if (lp == rp) {
			mx = mn = (ll)d*pos_add-v;
			return;
		}
		l->set_val(p, v);
		r->set_val(p, v);
		reupd();
	}
	void inc_pos(int lv, int rv) {
		if (lp > rv || rp < lv) return;
		if (lp >= lv && rp <= rv) {
			mx += d;
			mn += d;
			pos_add++;
			return;
		}
		l->inc_pos(lv, rv);
		r->inc_pos(lv, rv);
		reupd();
	}
};

typedef pair<int, int> pii;

const int MAXN = 2e5+5;

pii sortable[MAXN];
int cord[MAXN];
int pos[MAXN];

void print(ll ans) {
	cout << ans/2;
	if (ans&1) cout << ".5";
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n >> m >> d;
	m += n;
	for (int i = 0; i < m; i++) {
		cin >> cord[i];
		sortable[i].first = cord[i];
		sortable[i].second = i;
	}
	sort(sortable, sortable+m);
	for (int i = 0; i < m; i++) pos[sortable[i].second] = i;
	stree *tree = new stree(0, m-1);
	for (int i = 0; i < m; i++) {
		tree->set_val(pos[i], cord[i]);
		tree->inc_pos(pos[i]+1, m-1);
		if (i > n) cout << ' ';
		if (i >= n) print(max(0ll, tree->best));
	}
	cout << '\n';
}

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