oj.uz

Submission #641945

# Submission time Handle Problem Language Result Execution time Memory
641945 2022-09-18T00:01:58 Z Markomafko972 Measures (CEOI22_measures) C++14
59 / 100
 408 ms 42760 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;
	
		sol = max(sol, -hi+lo);
	
		/*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++) {
      |                  ~~^~~~~~~~~~
Main.cpp:103:6: warning: unused variable 'najl' [-Wunused-variable]
  103 |  int najl = 1e9, najr = -1e9;
      |      ^~~~
Main.cpp:103:18: warning: unused variable 'najr' [-Wunused-variable]
  103 |  int najl = 1e9, najr = -1e9;
      |                  ^~~~

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 33232 KB Output is correct
3 Correct 15 ms 33236 KB Output is correct
4 Correct 16 ms 33280 KB Output is correct
5 Correct 15 ms 33212 KB Output is correct
6 Correct 19 ms 33300 KB Output is correct
7 Correct 16 ms 33300 KB Output is correct
8 Correct 16 ms 33220 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 33232 KB Output is correct
3 Correct 15 ms 33236 KB Output is correct
4 Correct 16 ms 33280 KB Output is correct
5 Correct 15 ms 33212 KB Output is correct
6 Correct 19 ms 33300 KB Output is correct
7 Correct 16 ms 33300 KB Output is correct
8 Correct 16 ms 33220 KB Output is correct
9 Correct 408 ms 39560 KB Output is correct
10 Correct 381 ms 39488 KB Output is correct
11 Correct 310 ms 39548 KB Output is correct
12 Correct 341 ms 39492 KB Output is correct
13 Correct 300 ms 39516 KB Output is correct
14 Correct 329 ms 39536 KB Output is correct
15 Correct 392 ms 39552 KB Output is correct
16 Correct 314 ms 39656 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 304 ms 40580 KB Output is correct
2 Correct 318 ms 42564 KB Output is correct
3 Correct 319 ms 42524 KB Output is correct
4 Correct 312 ms 40572 KB Output is correct
5 Correct 312 ms 41576 KB Output is correct
6 Correct 308 ms 40708 KB Output is correct
7 Correct 309 ms 41728 KB Output is correct
8 Correct 309 ms 40532 KB Output is correct
9 Correct 309 ms 40328 KB Output is correct
10 Correct 320 ms 42760 KB Output is correct
11 Correct 309 ms 41192 KB Output is correct
12 Correct 308 ms 42224 KB Output is correct
13 Correct 306 ms 40296 KB Output is correct
14 Correct 306 ms 42348 KB Output is correct
15 Correct 309 ms 42108 KB Output is correct
16 Correct 302 ms 40300 KB Output is correct
17 Correct 313 ms 41648 KB Output is correct

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 304 ms 40580 KB Output is correct
2 Correct 318 ms 42564 KB Output is correct
3 Correct 319 ms 42524 KB Output is correct
4 Correct 312 ms 40572 KB Output is correct
5 Correct 312 ms 41576 KB Output is correct
6 Correct 308 ms 40708 KB Output is correct
7 Correct 309 ms 41728 KB Output is correct
8 Correct 309 ms 40532 KB Output is correct
9 Correct 309 ms 40328 KB Output is correct
10 Correct 320 ms 42760 KB Output is correct
11 Correct 309 ms 41192 KB Output is correct
12 Correct 308 ms 42224 KB Output is correct
13 Correct 306 ms 40296 KB Output is correct
14 Correct 306 ms 42348 KB Output is correct
15 Correct 309 ms 42108 KB Output is correct
16 Correct 302 ms 40300 KB Output is correct
17 Correct 313 ms 41648 KB Output is correct
18 Correct 399 ms 40868 KB Output is correct
19 Incorrect 392 ms 42384 KB Output isn't correct
20 Halted 0 ms 0 KB -