oj.uz

답안 #996343

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
996343 2024-06-10T13:26:34 Z 0npata Measures (CEOI22_measures) C++17
0 / 100
 1500 ms 20080 KB 
#include<bits/stdc++.h>
using namespace std;

#define vec vector
#define int long long

const int INF = 1e17;

struct SegTreeLazy {
	vec<int> data;
	int n;

	SegTreeLazy(int in) {
		int n = 1;
		while(n<in) n*=2;

		data = vec<int>(n);
	}

	void set(int i, int val) {
		data[i] = val;
	}
	int get(int i) {
		return data[i];
	}
	void upd(int l, int r, int val) {
		for(int i = l; i<r; i++) {
			data[i] += val;
		}
	}
};

int32_t main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int n, m, d;
	cin >> n >> m >> d;

	vec<int> a(n+m+2);
	for(int i = 0; i<n+m; i++) {
		cin >> a[i];
		a[i] *= 2;
	}
	d *= 2;
	a[n+m] = INF;
	a[n+m+1] = -INF;

	vec<int> ri(n+m+2);
	iota(ri.begin(), ri.end(), 0);

	sort(ri.begin(), ri.end(), [&] (int i, int j) { return a[i] < a[j]; });
	vec<int> ai(n+m+2);

	for(int i = 0; i<n+m+2; i++) {
		ai[ri[i]] = i;
	}

	multiset<int> ms;
	ms.insert(0);
	ms.insert(n+m+1);

	SegTreeLazy left_shift(n+m+2);
	SegTreeLazy right_shift(n+m+2);

	left_shift.set(0, -INF);
	left_shift.set(n+m+1, INF);
	right_shift.set(0, -INF);
	right_shift.set(n+m+1, INF);

	int topt = 0;

	for(int i = 0; i<n+m; i++) {
		int j = ai[i];

		ms.insert(j);

		auto it = ms.find(j);

		it--;
		int prev = *it;
		it++; it++;
		int nxt = *it;

		int l = left_shift.get(prev);
		int r = right_shift.get(nxt);

		assert(r >= l+d);

		int offs = 2*d-(r-l);

		if(offs >= 0) {
			topt += offs/2;
			left_shift.upd(1, j, -offs/2);
			right_shift.upd(j+1, n+m+1, offs/2);
			r += offs/2;
			l -= offs/2;
		}

		int ml = a[i]-topt;
		int mr = a[i]+topt;

		int mloffs = (r-d)-ml;
		int mroffs = (mr-(l+d));

		offs = min(mloffs, mroffs);

//		cerr << "----------------" << '\n';
//		cerr << "l: " << l << '\n';
//		cerr << "r: " << r << '\n';
//		cerr << "mloffs: " << mloffs << '\n';
//		cerr << "mroffs: " << mroffs << '\n';

		if(offs <= 0) {
			offs = -offs;
			topt += offs/2;
			left_shift.upd(1, j, -offs/2);
			right_shift.upd(j+1, n+m+1, offs/2);
			r += offs/2;
			l -= offs/2;
		}


		int mlpos = max(l+d, a[i]-topt);
		int mrpos = min(r-d, a[i]+topt);

		left_shift.set(j, mlpos);
		right_shift.set(j, mrpos);

		int lr = left_shift.get(nxt);
		int dist = mlpos+d-lr;
		if(dist > 0) {
			left_shift.upd(j+1, n+m+1, dist);
		}

		int rl = right_shift.get(prev);
		dist = rl-(mrpos-d);

		if(dist > 0) {
			right_shift.upd(1, j, -dist);
		}

		if(i >= n) cout << ((float)topt)/2 << ' ';
	}
	cout << '\n';
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1509 ms 20080 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1509 ms 20080 KB Time limit exceeded
2 Halted 0 ms 0 KB -