Submission #862922

#	Time	Username	Problem	Language	Result	Execution time	Memory
862922		Trisanu_Das	Measures (CEOI22_measures)	C++17	100 / 100	214 ms	34900 KiB

Main

#include <bits/stdc++.h>
#define int long long
using namespace std;
 
struct node{
	int mx, mn, ans;
};
 
const int N = 2e5, inf = 1e17;
 
node segt[4 * N + 5];
int lazy[4 * N + 5];
 
node merge(node a, node b){
	node c;
	c.ans = max({a.ans, b.ans, a.mx - b.mn});
	c.mx = max(a.mx, b.mx);
	c.mn = min(a.mn, b.mn);
	return c;
}
 
void update(int idx, int l, int r, int L, int R, int val){
	if (l > R or r < L) return;
	if (l >= L and r <= R){
		if (L == R) segt[idx] = {val + lazy[idx], val + lazy[idx], 0};
		else{
			segt[idx].mx += val;
			segt[idx].mn += val;
			lazy[idx] += val;
		}
		return;
	}
	for (int k : {2 * idx, 2 * idx + 1}){
		segt[k].mn += lazy[idx];
		segt[k].mx += lazy[idx];
		lazy[k] += lazy[idx];
	}
	lazy[idx] = 0;
	int mid = (l + r) / 2;
	update(2 * idx, l, mid, L, R, val);
	update(2 * idx + 1, mid + 1, r, L, R, val);
	segt[idx] = merge(segt[2 * idx], segt[2 * idx + 1]);
}
 
signed main(){
	ios::sync_with_stdio(false); cin.tie(NULL);
	int n, m, d; cin >> n >> m >> d;
	fill_n(segt, 4 * N + 5, node{-INT_MIN, INT_MAX, INT_MIN});
	vector<int> init(n + m), to(n + m);
	vector<pair<int,int>> a(n + m); 
	for (int i = 0; i < n + m; i++){
		cin >> init[i];
		a[i] = {init[i], i};
	}
	sort(a.begin(),a.end());
	for (int i = 0; i < n + m; i++) to[a[i].second] = i;
	for (int i = 0; i < n + m; i++){
		int pos = to[i];
		update(1, 0, n + m + 4, pos, pos, init[i]);
		update(1, 0, n + m + 4, pos + 1, n + m + 4, -d);
		if (i >= n){
			int ans = segt[1].ans;
			cout << ans/2;
			if (ans & 1) cout << ".5";
			cout << ' ';
		}
	}
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:48:31: warning: integer overflow in expression of type 'int' results in '-2147483648' [-Woverflow]
   48 |  fill_n(segt, 4 * N + 5, node{-INT_MIN, INT_MAX, INT_MIN});
      |                               ^

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