oj.uz

Submission #1044006

# Submission time Handle Problem Language Result Execution time Memory
1044006 2024-08-05T06:21:33 Z ㄴㄴ(#11063) Measures (CEOI22_measures) C++17
0 / 100
 226 ms 25796 KB 
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
using ll = long long;
const ll INF = 1e18;

struct node {
	ll l, r, v;
	int c;
} T[535353];
ll L[535353];
const node EMP = {INF, -INF, 0, 0};

node operator +(node p, node q) {
	node ret;
	ret.l = min(p.l, q.l);
	ret.r = max(p.r, q.r);
	ret.v = max({p.v, q.v, p.r - q.l});
	ret.c = p.c + q.c;
	return ret;
}

void push(int idx, int s, int e) {
	if(L[idx]) {
		T[idx].l += L[idx];
		T[idx].r += L[idx];
		if(s != e) {
			L[idx*2] += L[idx];
			L[idx*2+1] += L[idx];
		}
		L[idx] = 0;
	}
}

node get(int idx, int s, int e, int l, int r) {
	push(idx, s, e);
	if(r < s || e < l) return EMP;
	if(l <= s && e <= r) return T[idx];
	int m = s+e >> 1;
	return get(idx*2, s, m, l, r) + get(idx*2+1, m+1, e, l, r);
}

void upd(int idx, int s, int e, int l, int r, int v) {
	push(idx, s, e);
	if(r < s || e < l) return;
	if(l <= s && e <= r) {
		L[idx] += v;
		push(idx, s, e);
		return;
	}
	int m = s+e >> 1;
	upd(idx*2, s, m, l, r, v);
	upd(idx*2+1, m+1, e, l, r, v);
	T[idx] = T[idx*2] + T[idx*2+1];
}

void add(int idx, int s, int e, int p, node v) {
	push(idx, s, e);
	if(p < s || e < p) return;
	if(s == e) {
		T[idx] = v;
		return;
	}
	int m = s+e >> 1;
	add(idx*2, s, m, p, v);
	add(idx*2+1, m+1, e, p, v);
	T[idx] = T[idx*2] + T[idx*2+1];
}

int I[202020];

int main() {
	int N, M, D; scanf("%d%d%d", &N, &M, &D);
	for(int i=0; i<535353; i++) T[i] = EMP;
	vector<pii> A(N+M);
	for(int i=0; i<N+M; i++) {
		scanf("%d", &A[i].first);
		A[i].second = i;
	}
	sort(A.begin(), A.end());
	for(int i=0; i<N+M; i++) I[A[i].second] = i+1;
	sort(A.begin(), A.end(), [&](pii p, pii q) { return p.second < q.second; });
	for(int i=0; i<N+M; i++) {
		auto [x, y] = A[i];
		int j = get(1, 1, N+M, 1, I[y]).c;
		upd(1, 1, N+M, I[y], N+M, -D);
		add(1, 1, N+M, I[y], {x - 1LL*D*j, x - 1LL*D*j, 0, 1});
		if(i >= N) {
			int ans = get(1, 1, N+M, 1, N+M).v;
			if(ans % 2) printf("%d.5 ", ans / 2);
			else printf("%d ", ans / 2);
		}
	}
	return 0;
}

Compilation message

Main.cpp: In function 'node get(int, int, int, int, int)':
Main.cpp:39:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |  int m = s+e >> 1;
      |          ~^~
Main.cpp: In function 'void upd(int, int, int, int, int, int)':
Main.cpp:51:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   51 |  int m = s+e >> 1;
      |          ~^~
Main.cpp: In function 'void add(int, int, int, int, node)':
Main.cpp:64:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 |  int m = s+e >> 1;
      |          ~^~
Main.cpp: In function 'int main()':
Main.cpp:73:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |  int N, M, D; scanf("%d%d%d", &N, &M, &D);
      |               ~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:77:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |   scanf("%d", &A[i].first);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 17752 KB Output is correct
2 Correct 3 ms 17756 KB Output is correct
3 Correct 3 ms 17948 KB Output is correct
4 Correct 3 ms 17756 KB Output is correct
5 Correct 4 ms 17756 KB Output is correct
6 Correct 4 ms 17756 KB Output is correct
7 Correct 3 ms 17756 KB Output is correct
8 Incorrect 4 ms 17968 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 17752 KB Output is correct
2 Correct 3 ms 17756 KB Output is correct
3 Correct 3 ms 17948 KB Output is correct
4 Correct 3 ms 17756 KB Output is correct
5 Correct 4 ms 17756 KB Output is correct
6 Correct 4 ms 17756 KB Output is correct
7 Correct 3 ms 17756 KB Output is correct
8 Incorrect 4 ms 17968 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 226 ms 24596 KB Output is correct
2 Incorrect 195 ms 25796 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 226 ms 24596 KB Output is correct
2 Incorrect 195 ms 25796 KB Output isn't correct
3 Halted 0 ms 0 KB -