oj.uz

Submission #641944

# Submission time Handle Problem Language Result Execution time Memory
641944 2022-09-17T23:55:33 Z Markomafko972 Measures (CEOI22_measures) C++14
59 / 100
 419 ms 42772 KB 
#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 = 2*OFF-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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 33236 KB Output is correct
2 Correct 16 ms 33236 KB Output is correct
3 Correct 16 ms 33236 KB Output is correct
4 Correct 18 ms 33236 KB Output is correct
5 Correct 16 ms 33196 KB Output is correct
6 Correct 17 ms 33236 KB Output is correct
7 Correct 18 ms 33304 KB Output is correct
8 Correct 17 ms 33256 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 33236 KB Output is correct
2 Correct 16 ms 33236 KB Output is correct
3 Correct 16 ms 33236 KB Output is correct
4 Correct 18 ms 33236 KB Output is correct
5 Correct 16 ms 33196 KB Output is correct
6 Correct 17 ms 33236 KB Output is correct
7 Correct 18 ms 33304 KB Output is correct
8 Correct 17 ms 33256 KB Output is correct
9 Correct 412 ms 39564 KB Output is correct
10 Correct 389 ms 39508 KB Output is correct
11 Correct 309 ms 39564 KB Output is correct
12 Correct 354 ms 39644 KB Output is correct
13 Correct 307 ms 39600 KB Output is correct
14 Correct 337 ms 39732 KB Output is correct
15 Correct 407 ms 39612 KB Output is correct
16 Correct 311 ms 39660 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 316 ms 40580 KB Output is correct
2 Correct 316 ms 42656 KB Output is correct
3 Correct 321 ms 42492 KB Output is correct
4 Correct 310 ms 40384 KB Output is correct
5 Correct 375 ms 41612 KB Output is correct
6 Correct 305 ms 40828 KB Output is correct
7 Correct 332 ms 41648 KB Output is correct
8 Correct 308 ms 40360 KB Output is correct
9 Correct 323 ms 40320 KB Output is correct
10 Correct 310 ms 42772 KB Output is correct
11 Correct 321 ms 41176 KB Output is correct
12 Correct 368 ms 42048 KB Output is correct
13 Correct 310 ms 40300 KB Output is correct
14 Correct 315 ms 42360 KB Output is correct
15 Correct 310 ms 42176 KB Output is correct
16 Correct 328 ms 40304 KB Output is correct
17 Correct 313 ms 41696 KB Output is correct

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 316 ms 40580 KB Output is correct
2 Correct 316 ms 42656 KB Output is correct
3 Correct 321 ms 42492 KB Output is correct
4 Correct 310 ms 40384 KB Output is correct
5 Correct 375 ms 41612 KB Output is correct
6 Correct 305 ms 40828 KB Output is correct
7 Correct 332 ms 41648 KB Output is correct
8 Correct 308 ms 40360 KB Output is correct
9 Correct 323 ms 40320 KB Output is correct
10 Correct 310 ms 42772 KB Output is correct
11 Correct 321 ms 41176 KB Output is correct
12 Correct 368 ms 42048 KB Output is correct
13 Correct 310 ms 40300 KB Output is correct
14 Correct 315 ms 42360 KB Output is correct
15 Correct 310 ms 42176 KB Output is correct
16 Correct 328 ms 40304 KB Output is correct
17 Correct 313 ms 41696 KB Output is correct
18 Correct 406 ms 40936 KB Output is correct
19 Incorrect 419 ms 42460 KB Output isn't correct
20 Halted 0 ms 0 KB -