Submission #641937

#	Time	Username	Problem	Language	Result	Execution time	Memory
641937		Markomafko972	Measures (CEOI22_measures)	C++14	59 / 100	423 ms	30804 KiB

Main

#include <bits/stdc++.h>
#define X first
#define Y second
#define pb push_back
#define pii pair<int, int>
typedef long long ll;
using namespace std;

const int MOD = 1e9 + 7;
const ll INF = 1e18;
const int OFF = (1 << 20);

int n, m, d;
int a[250005];
int pos[250005];
vector< pair<int, int> > v;

pair<ll, ll> t[2*OFF+5];
ll p[2*OFF+5];

void prop(int x) {
	if (p[x] == 0 || x >= OFF) return;
	
	t[x*2].X += p[x];
	t[x*2+1].X += p[x];
	t[x*2].Y += p[x];
	t[x*2+1].Y += p[x];
	p[x*2] += p[x];
	p[x*2+1] += p[x];
	p[x] = 0;
	return;
}

ll query(int a, int b, int l, int r, int x) {
	if (r <= a || b <= l) {
		if (a == 0) return -INF;
		return INF;
	}
	if (a <= l && r <= b) {
		if (a == 0) return t[x].Y;
		return t[x].X;
	}
	
	prop(x);
	
	ll o1 = query(a, b, l, (l+r)/2, x*2);
	ll o2 = query(a, b, (l+r)/2, r, x*2+1);
	
	//cout << o1 << " " << o2 << endl;
	
	if (a == 0) return max(o1, o2);
	return min(o1, o2);
}

void update(int a, int b, int l, int r, int x, ll kol) {
	if (r <= a || b <= l) return;
	if (a <= l && r <= b) {
		if (kol == INF+1) {
			t[x].X += -INF;
			t[x].Y += INF;
			return;
		}
		
		t[x].X += kol;
		t[x].Y += kol;
		p[x] += kol;
		return;
	}
	
	prop(x);
	
	update(a, b, l, (l+r)/2, x*2, kol);
	update(a, b, (l+r)/2, r, x*2+1, kol);
	t[x].X = min(t[x*2].X, t[x*2+1].X);
	t[x].Y = max(t[x*2].Y, t[x*2+1].Y);
}

int main () {

	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n >> m >> d;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		v.push_back({a[i], i});
	}
	for (int i = n; i < n+m; i++) {
		cin >> a[i];
		v.push_back({a[i], i});
	}
	sort(v.begin(), v.end());
	for (int i = 0; i < v.size(); i++) {
		pos[v[i].Y] = i;
	}
	
	for (int i = OFF+n+m-1; i > 0; i--) {
		t[i].X = INF;
		t[i].Y = -INF;
	}
	
	ll sol = 0;
	int najl = 1e9, najr = -1e9;
	for (int i = 0; i < n+m; i++) {
		update(pos[i], pos[i]+1, 0, OFF, 1, INF+1);
		
		update(pos[i], pos[i]+1, 0, OFF, 1, a[i]);
		update(pos[i]+1, n+m, 0, OFF, 1, -d);
		
		ll lo = query(0, pos[i]+1, 0, OFF, 1);
		ll hi = query(pos[i], n+m, 0, OFF, 1);
		
		//cout << i << ": " << lo << " " << hi << " " << pos[i] << " " << query(pos[i], pos[i]+1, 0, OFF, 1) << endl;
	
		if (najl == 1e9 && najr == -1e9) {
			najl = pos[i];
			najr = pos[i];
		}
		else if (pos[i] >= najl || pos[i] <= najr) sol = max(sol, -hi+lo);
		else if (pos[i] > najr) {
			sol = max(sol, (ll)pos[i]*(ll)d-a[i]+lo);
			najr = pos[i];
		}
		else if (pos[i] < najl) {
			sol = max(sol, -hi+a[i]-(ll)pos[i]*(ll)d);
			najl = pos[i];
		}
	
		if (i >= n) {
			cout << sol/2;
			if (sol % 2 == 1) cout << ".5";
			cout << " ";
		}
	}
	
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:93:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |  for (int i = 0; i < v.size(); i++) {
      |                  ~~^~~~~~~~~~

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