oj.uz

답안 #641937

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
641937 2022-09-17T23:25:57 Z Markomafko972 Measures (CEOI22_measures) C++14
59 / 100
 423 ms 30804 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 = 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

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

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 16852 KB Output is correct
2 Correct 10 ms 16852 KB Output is correct
3 Correct 10 ms 16912 KB Output is correct
4 Correct 11 ms 16860 KB Output is correct
5 Correct 9 ms 16852 KB Output is correct
6 Correct 10 ms 16860 KB Output is correct
7 Correct 13 ms 16856 KB Output is correct
8 Correct 10 ms 16852 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 16852 KB Output is correct
2 Correct 10 ms 16852 KB Output is correct
3 Correct 10 ms 16912 KB Output is correct
4 Correct 11 ms 16860 KB Output is correct
5 Correct 9 ms 16852 KB Output is correct
6 Correct 10 ms 16860 KB Output is correct
7 Correct 13 ms 16856 KB Output is correct
8 Correct 10 ms 16852 KB Output is correct
9 Correct 408 ms 27592 KB Output is correct
10 Correct 396 ms 27800 KB Output is correct
11 Correct 324 ms 27208 KB Output is correct
12 Correct 354 ms 27420 KB Output is correct
13 Correct 314 ms 27060 KB Output is correct
14 Correct 344 ms 27108 KB Output is correct
15 Correct 395 ms 27032 KB Output is correct
16 Correct 328 ms 26600 KB Output is correct

Subtask #3
35.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 313 ms 27324 KB Output is correct
2 Correct 326 ms 30484 KB Output is correct
3 Correct 325 ms 30184 KB Output is correct
4 Correct 319 ms 27648 KB Output is correct
5 Correct 309 ms 29672 KB Output is correct
6 Correct 347 ms 28648 KB Output is correct
7 Correct 317 ms 29896 KB Output is correct
8 Correct 320 ms 28840 KB Output is correct
9 Correct 316 ms 28284 KB Output is correct
10 Correct 319 ms 30804 KB Output is correct
11 Correct 314 ms 28988 KB Output is correct
12 Correct 322 ms 30124 KB Output is correct
13 Correct 323 ms 28052 KB Output is correct
14 Correct 317 ms 30336 KB Output is correct
15 Correct 332 ms 30012 KB Output is correct
16 Correct 311 ms 28264 KB Output is correct
17 Correct 327 ms 29624 KB Output is correct

Subtask #4
0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Correct 313 ms 27324 KB Output is correct
2 Correct 326 ms 30484 KB Output is correct
3 Correct 325 ms 30184 KB Output is correct
4 Correct 319 ms 27648 KB Output is correct
5 Correct 309 ms 29672 KB Output is correct
6 Correct 347 ms 28648 KB Output is correct
7 Correct 317 ms 29896 KB Output is correct
8 Correct 320 ms 28840 KB Output is correct
9 Correct 316 ms 28284 KB Output is correct
10 Correct 319 ms 30804 KB Output is correct
11 Correct 314 ms 28988 KB Output is correct
12 Correct 322 ms 30124 KB Output is correct
13 Correct 323 ms 28052 KB Output is correct
14 Correct 317 ms 30336 KB Output is correct
15 Correct 332 ms 30012 KB Output is correct
16 Correct 311 ms 28264 KB Output is correct
17 Correct 327 ms 29624 KB Output is correct
18 Correct 412 ms 29164 KB Output is correct
19 Incorrect 423 ms 30452 KB Output isn't correct
20 Halted 0 ms 0 KB -