oj.uz

답안 #641946

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
641946 2022-09-18T00:11:54 Z Markomafko972 Measures (CEOI22_measures) C++14
100 / 100
 425 ms 44224 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, int ty) {
	if (r <= a || b <= l) {
		if (ty == 0) return -INF;
		return INF;
	}
	if (a <= l && r <= b) {
		if (ty == 0) return t[x].Y;
		return t[x].X;
	}
	
	prop(x);
	
	ll o1 = query(a, b, l, (l+r)/2, x*2, ty);
	ll o2 = query(a, b, (l+r)/2, r, x*2+1, ty);
	
	//cout << o1 << " " << o2 << endl;
	
	if (ty == 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, 0);
		ll hi = query(pos[i], n+m, 0, OFF, 1, 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

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 33236 KB Output is correct
2 Correct 16 ms 33240 KB Output is correct
3 Correct 19 ms 33212 KB Output is correct
4 Correct 17 ms 33192 KB Output is correct
5 Correct 19 ms 33200 KB Output is correct
6 Correct 16 ms 33272 KB Output is correct
7 Correct 17 ms 33236 KB Output is correct
8 Correct 16 ms 33236 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 33236 KB Output is correct
2 Correct 16 ms 33240 KB Output is correct
3 Correct 19 ms 33212 KB Output is correct
4 Correct 17 ms 33192 KB Output is correct
5 Correct 19 ms 33200 KB Output is correct
6 Correct 16 ms 33272 KB Output is correct
7 Correct 17 ms 33236 KB Output is correct
8 Correct 16 ms 33236 KB Output is correct
9 Correct 425 ms 39564 KB Output is correct
10 Correct 407 ms 39508 KB Output is correct
11 Correct 351 ms 39516 KB Output is correct
12 Correct 403 ms 39608 KB Output is correct
13 Correct 310 ms 39588 KB Output is correct
14 Correct 339 ms 39484 KB Output is correct
15 Correct 393 ms 39608 KB Output is correct
16 Correct 333 ms 39640 KB Output is correct

Subtask #3
35.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 306 ms 40644 KB Output is correct
2 Correct 320 ms 42524 KB Output is correct
3 Correct 356 ms 42492 KB Output is correct
4 Correct 324 ms 40292 KB Output is correct
5 Correct 315 ms 41576 KB Output is correct
6 Correct 314 ms 40724 KB Output is correct
7 Correct 376 ms 41632 KB Output is correct
8 Correct 333 ms 40400 KB Output is correct
9 Correct 308 ms 40372 KB Output is correct
10 Correct 338 ms 42796 KB Output is correct
11 Correct 314 ms 41212 KB Output is correct
12 Correct 328 ms 42180 KB Output is correct
13 Correct 307 ms 40324 KB Output is correct
14 Correct 321 ms 42344 KB Output is correct
15 Correct 309 ms 42148 KB Output is correct
16 Correct 316 ms 40400 KB Output is correct
17 Correct 310 ms 41640 KB Output is correct

Subtask #4
41.0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Correct 306 ms 40644 KB Output is correct
2 Correct 320 ms 42524 KB Output is correct
3 Correct 356 ms 42492 KB Output is correct
4 Correct 324 ms 40292 KB Output is correct
5 Correct 315 ms 41576 KB Output is correct
6 Correct 314 ms 40724 KB Output is correct
7 Correct 376 ms 41632 KB Output is correct
8 Correct 333 ms 40400 KB Output is correct
9 Correct 308 ms 40372 KB Output is correct
10 Correct 338 ms 42796 KB Output is correct
11 Correct 314 ms 41212 KB Output is correct
12 Correct 328 ms 42180 KB Output is correct
13 Correct 307 ms 40324 KB Output is correct
14 Correct 321 ms 42344 KB Output is correct
15 Correct 309 ms 42148 KB Output is correct
16 Correct 316 ms 40400 KB Output is correct
17 Correct 310 ms 41640 KB Output is correct
18 Correct 423 ms 40796 KB Output is correct
19 Correct 393 ms 42404 KB Output is correct
20 Correct 319 ms 44224 KB Output is correct
21 Correct 340 ms 42056 KB Output is correct
22 Correct 356 ms 42404 KB Output is correct
23 Correct 347 ms 42316 KB Output is correct
24 Correct 399 ms 42568 KB Output is correct
25 Correct 312 ms 42160 KB Output is correct
26 Correct 399 ms 41772 KB Output is correct
27 Correct 416 ms 43776 KB Output is correct
28 Correct 346 ms 42432 KB Output is correct
29 Correct 365 ms 42256 KB Output is correct
30 Correct 341 ms 41212 KB Output is correct
31 Correct 339 ms 43616 KB Output is correct
32 Correct 338 ms 42916 KB Output is correct
33 Correct 394 ms 40512 KB Output is correct
34 Correct 357 ms 41988 KB Output is correct