Submission #1303118

#	Time	Username	Problem	Language	Result	Execution time	Memory
1303118		Jawad_Akbar_JJ	Measures (CEOI22_measures)	C++20	100 / 100	199 ms	27324 KiB

Main

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
#define int long long
const int N = (1<<18) + 1, inf = 1e17;
int ft[N], a[N], Id[N];

void Add(int i){
	for (; i < N; i += i&-i)
		ft[i]++;
}

int get(int i, int ans = 0){
	for (; i; i -= i&-i)
		ans += ft[i];
	return ans;
}

struct node{
	int cnt = 0, Ans = 0, Lz = 0, Min = inf, Max = -inf;
} seg[N<<1];

void Upd(int cur, int vl){
	seg[cur].Lz += vl;
	seg[cur].Min += vl;
	seg[cur].Max += vl;
}

void Push(int cur, int lc, int rc){
	Upd(lc, seg[cur].Lz);
	Upd(rc, seg[cur].Lz);
	seg[cur].Lz = 0;
}

node merge(node A, node B){
	node C;
	C.Ans = max(A.Max - B.Min, max(A.Ans, B.Ans));
	C.Max = max(A.Max, B.Max);
	C.Min = min(A.Min, B.Min);
	C.cnt = A.cnt + B.cnt;
	return C;
}

void insert(int i, int vl, int cur = 1, int st = 1, int en = N){
	if (i >= en or i < st)
		return;
	if (en - st == 1){
		seg[cur].cnt = 1;
		seg[cur].Min = seg[cur].Max = vl;
		return;
	}
	int lc = cur + cur, rc = lc + 1, mid = (st + en) / 2;
	Push(cur, lc, rc);
	insert(i, vl, lc, st, mid);
	insert(i, vl, rc, mid, en);

	seg[cur] = merge(seg[lc], seg[rc]);
}

void Update(int l, int r, int v, int cur = 1, int st = 1, int en = N){
	if (l >= en or r <= st)
		return;
	if (l <= st and r >= en){
		Upd(cur, v);
		return;
	}
	int lc = cur + cur, rc = lc + 1, mid = (st + en) / 2;
	Push(cur, lc, rc);
	Update(l, r, v, lc, st, mid);
	Update(l, r, v, rc, mid, en);

	seg[cur] = merge(seg[lc], seg[rc]);
}

signed main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int n, m, d;
	cin>>n>>m>>d, m += n;

	vector<pair<int, int>> vec;
	for (int i=1;i<=m;i++){
		cin>>a[i];
		vec.push_back({a[i], i});
	}
	sort(begin(vec), end(vec));

	for (int i=1;i<=m;i++)
		Id[vec[i-1].second] = i;	

	for (int i=1;i<=m;i++){
		insert(Id[i], a[i] - get(Id[i]) * d);
		Update(Id[i], N, -d);
		Add(Id[i]);

		if (i > n){
			cout<<seg[1].Ans / 2;
			if (seg[1].Ans % 2)
				cout<<".5";
			cout<<' ';
		}
	}
	cout<<'\n';
}

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