Submission #799256

#	Time	Username	Problem	Language	Result	Execution time	Memory
799256		IvanJ	Measures (CEOI22_measures)	C++17	100 / 100	287 ms	28588 KiB

Main

#include<bits/stdc++.h>

#define pb push_back
#define x first
#define y second
#define all(a) (a).begin(), (a).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;

const int maxn = 4e5 + 5;
const ll inf = 1e18;

struct Data {
	ll ans, cnt, mini, maxi;
};

Data merge(Data A, Data B) {
	if(B.cnt == 0) return A;
	if(A.cnt == 0) return B;
	Data ret;
	ret.ans = max(A.ans, B.ans);
	ret.ans = max(ret.ans, B.maxi - A.mini);
	ret.cnt = A.cnt + B.cnt;
	ret.mini = min(A.mini, B.mini);
	ret.maxi = max(A.maxi, B.maxi);
	return ret;
}

int n, m, d;
int A[maxn];
int B[maxn];
vector<int> vals;

struct Seg {
	int pot;
	vector<ll> L;
	vector<Data> T;
	void init(int sz) {
		pot = 1;
		while(pot < sz) pot <<= 1;
		L = vector<ll>(pot << 1, 0);
		T = vector<Data>(pot << 1, {0, 0, 0, 0});
	}
	
	void prop(int x) {
		if(L[x] == 0) return;
		T[x].mini += L[x], T[x].maxi += L[x];
		if(x < pot) 
			L[x * 2] += L[x], L[x * 2 + 1] += L[x];
		L[x] = 0;
	}
	
	void update(int x, int lo, int hi, int a, int b, ll v) {
		prop(x);
		if(hi < a || b < lo) return;
		if(a <= lo && hi <= b) {
			if(v < 0) T[x].cnt = 1;
			L[x] += v;
			prop(x);
			return;
		}
		int mid = (lo + hi) / 2;
		update(x * 2, lo, mid, a, b, v);
		update(x * 2 + 1, mid + 1, hi, a, b, v);
		T[x] = merge(T[x * 2], T[x * 2 + 1]);
	}
	
	void add(int x) {
		update(1, 0, pot - 1, x, x, -vals[x]);
		update(1, 0, pot - 1, x + 1, pot - 1, d);
	}
	
	ll query(int x, int lo, int hi, int a) {
		prop(x);
		if(lo == hi) return T[x].mini;
		int mid = (lo + hi) / 2;
		if(a <= mid)
			return query(x * 2, lo, mid, a);
		return query(x * 2 + 1, mid + 1, hi, a);
	}
	
	void get() {
		ll sol = T[1].ans;
		if(sol & 1) printf("%lld.5 ", sol / 2);
		else printf("%lld ", sol / 2);
	}
} S;

void compress() {
	vector<pair<int, ii>> v;
	for(int i = 0;i < n;i++) 
		v.pb({A[i], {0, i}});
	for(int i = 0;i < m;i++) 
		v.pb({B[i], {1, i}});
	sort(all(v));
	for(int i = 0;i < n + m;i++) {
		vals.pb(v[i].x);
		if(v[i].y.x == 0) A[v[i].y.y] = i;
		if(v[i].y.x == 1) B[v[i].y.y] = i;
	} 
}

int main() {
	scanf("%d%d%d", &n, &m, &d);
	for(int i = 0;i < n;i++) 
		scanf("%d", A + i);
	for(int i = 0;i < m;i++) 
		scanf("%d", B + i);
	
	compress();
	S.init(n + m + 1);
	for(int i = 0;i < n;i++) S.add(A[i]);
	for(int i = 0;i < m;i++) S.add(B[i]), S.get();
	printf("\n");
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:107:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |  scanf("%d%d%d", &n, &m, &d);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:109:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |   scanf("%d", A + i);
      |   ~~~~~^~~~~~~~~~~~~
Main.cpp:111:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |   scanf("%d", B + i);
      |   ~~~~~^~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 14 / 14
• Subtask 3: 35 / 35
• Subtask 4: 41 / 41