제출 #1313762

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1313762		vlomaczk	Measures (CEOI22_measures)	C++20	45 / 100	79 ms	34424 KiB

Main

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

ll base = 1<<19;
ll inf = 1e18;
vector<ll> T(2*base,0), mi(2*base,inf), ma(2*base,-inf); // answer, max value K[x], min value K[x]

void merge(ll v, ll l, ll r) { // Calculates max over i < j of K[j] - K[i] where K[x] = D*x + pos
	T[v] = max(T[l], T[r]);
	T[v] = max(T[v], ma[r] - mi[l]);
	ma[v] = max(ma[r], ma[l]);
	mi[v] = min(mi[r], mi[l]);
}

ll D;

void update(ll x, ll val) {
	x += base;
	mi[x] = ma[x] = D*(x-base) - val;
	x/=2;
	while(x > 0) {
		merge(x,2*x,2*x+1);
		x/=2;
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	ll n, m;
	cin >> n >> m >> D;
	vector<ll> x(n), y(m);
	for(ll i=0; i<n; ++i) cin >> x[i];
	for(ll i=0; i<m; ++i) cin >> y[i];
	vector<pair<ll, ll>> pary;
	for(ll i=0; i<n; ++i) {
		pary.push_back({x[i], i});
	}
	for(ll i=0; i<m; ++i) {
		pary.push_back({y[i], i+n});
	}
	sort(pary.begin(), pary.end());
	ll cnt = 0;
	vector<ll> idx(n+m);
	for(auto[a,b] : pary) {
		idx[b] = cnt++;
	}	
	for(ll i=0; i<n; ++i) update(idx[i], x[i]);
	for(ll i=0; i<m; ++i) {
		update(idx[i+n], y[i]);
		cout << T[1]/2;
		if(T[1]%2==1) cout << ".5";
		cout << " ";
	}
	cout << "\n";

	return 0;
}

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