Submission #696090

#	Time	Username	Problem	Language	Result	Execution time	Memory
696090		Kahou	Measures (CEOI22_measures)	C++14	100 / 100	184 ms	33728 KiB

Main

/* In the name of God, aka Allah */
// let this be mytemp.cpp
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define endl '\n'
#define mk make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int N = 2e5 + 50;
ll n, m, k, d, a[N];
vector<ll> vc;

struct node {
	ll out, pre, suf, cnt;
	node() {
		out = pre = suf = cnt = 0;
	}
} seg[N<<2];

void upd(int id, int u=1, int tl=1, int tr=k) {
	if (tl == tr) {
		seg[u].cnt++;
		seg[u].pre = seg[u].cnt*d;
		seg[u].suf = seg[u].cnt*d;
		seg[u].out = (seg[u].cnt-1)*d;
		return;
	}
	int md = (tl+tr)>>1;
	int lc = u<<1;
	int rc = u<<1|1;
	if (id <= md) upd(id, lc, tl, md);
	else upd(id, rc, md+1, tr);
	
	seg[u].out = max(max(seg[lc].out, seg[rc].out), seg[lc].suf+seg[rc].pre-(vc[md+1]-vc[md])-d);
	seg[u].cnt = seg[lc].cnt + seg[rc].cnt;
	seg[u].pre = max(seg[lc].pre, seg[rc].pre-(vc[md+1]-vc[tl])+d*seg[lc].cnt);
	seg[u].suf = max(seg[rc].suf, seg[lc].suf-(vc[tr]-vc[md])+d*seg[rc].cnt);
}

void solve() {
	cin >> n >> m >> d;
	for (int i = 1; i <= n+m; i++) {
		cin >> a[i];
		vc.push_back(a[i]);
	}
	vc.push_back(0);
	sort(vc.begin(), vc.end());
	vc.resize(unique(vc.begin(), vc.end())-vc.begin());
	k = vc.size()-1;
	for (int i = 1; i <= n+m; i++) {
		int id = lower_bound(vc.begin(), vc.end(), a[i])-vc.begin();
		upd(id);
		if (i > n) {
			cout << seg[1].out/2;
			if (seg[1].out&1) cout << ".5";
			cout << ' ';
		}
	}
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	solve();
	return 0;
}

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