oj.uz

Submission #818501

# Submission time Handle Problem Language Result Execution time Memory
818501 2023-08-10T05:07:12 Z ono_de206 Measures (CEOI22_measures) C++14
100 / 100
 308 ms 29964 KB 
#include<bits/stdc++.h>
using namespace std;

#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define in insert
#define all(x) x.begin(),x.end()
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second

#define int long long
 
typedef long long ll;
typedef vector<int> vi;
typedef set<int> si;
typedef multiset<int> msi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;

template<typename T, typename U>
ostream & operator << (ostream &out, const pair<T, U> &c) {
	out << c.first << ' ' << c.second;
    return out;
}

template<typename T>
ostream & operator << (ostream &out, vector<T> &v) {
	const int sz = v.size();
	for (int i = 0; i < sz; i++) {
		if (i) out << ' ';
		out << v[i];
	}
    return out;
}

template<typename T>
istream & operator >> (istream &in, vector<T> &v) {
	for (T &x : v) in >> x;
    return in;
}


template<typename T>
void mxx(T &a, T b){if(b > a) a = b;}
template<typename T>
void mnn(T &a, T b){if(b < a) a = b;}

const int mxn = 4e5 + 10, inf = 1e18 + 10;
int a[mxn], id[mxn], d[mxn * 4], lz[mxn * 4], mn[mxn * 4], mx[mxn * 4], fn[mxn], t;

void pro(int i, int l, int r) {
	mn[i] += lz[i];
	mx[i] += lz[i];
	if(l < r) {
		lz[i * 2] += lz[i];
		lz[i * 2 + 1] += lz[i];
	}
	lz[i] = 0;
}

void up(int i, int l, int r) {
	if(l == r) return;
	int m = (l + r) / 2;
	pro(i * 2, l, m);
	pro(i * 2 + 1, m + 1, r);
	d[i] = max(d[i * 2], d[i * 2 + 1]);
	mxx(d[i], mx[i * 2] - mn[i * 2 + 1]);
	mx[i] = max(mx[i * 2], mx[i * 2 + 1]);
	mn[i] = min(mn[i * 2], mn[i * 2 + 1]);
}

void build(int l, int r, int i) {
	mn[i] = inf;
	mx[i] = -inf;
	d[i] = lz[i] = 0;
	if(l == r) return;
	int m = (l + r) >> 1;
	build(l, m, i * 2);
	build(m + 1, r, i * 2 + 1);
}

void assign(int l, int r, int i, int x, int val) {
	pro(i, l, r);
	if(l == r) {
		mn[i] = mx[i] = val;
		d[i] = 0;
		return;
	}
	int m = (l + r) >> 1;
	if(x <= m) assign(l, m, i * 2, x, val);
	else assign(m + 1, r, i * 2 + 1, x, val);
	up(i, l, r);
}

void update(int l, int r, int i, int x, int y, int val) {
	if(x > y) return;
	pro(i, l, r);
	if(l >= x && r <= y) {
		lz[i] += val;
		pro(i, l, r);
		return;
	}
	int m = (l + r) / 2;
	if(x <= m) update(l, m, i * 2, x, y, val);
	if(y > m) update(m + 1, r, i * 2 + 1, x, y, val);
	up(i, l, r);
}

int get(int i) {
	int ret = 0;
	for(; i; i -= (i & -i)) {
		ret += fn[i];
	}
	return ret;
}

void up(int i) {
	for(; i <= t; i += (i & -i)) {
		fn[i]++;
	}
}

string getAns() {
	int ans = d[1];
	string str = to_string(ans / 2);
	if(ans & 1) str += ".5";
	return str;
}

void go() {
	int n, m, d;
	cin >> n >> m >> d;
	vector<pair<int, int>> comp;
	for(int i = 1; i <= n + m; i++) {
		cin >> a[i];
		comp.eb(a[i], i);
	}
	sort(all(comp));
	t = 0;
	for(auto it : comp) {
		id[it.ss] = ++t;
	}
	build(1, t, 1);
	for(int i = 1; i <= n + m; i++) {
		int cnt = get(id[i]);
		up(id[i]);
		assign(1, t, 1, id[i], a[i] - cnt * d);
		update(1, t, 1, id[i] + 1, t, -d);
		if(i > n) cout << getAns() << ' ';
	}
}

signed main() {
	// #ifndef ONO
	// freopen("file.in", "r", stdin);
	// freopen("file.out", "w", stdout);
	// #endif
	fast;
	int T = 1;
	// cin >> t;
	while(T--) {
		go();
	}
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 2 ms 520 KB Output is correct
5 Correct 2 ms 596 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 2 ms 596 KB Output is correct
8 Correct 2 ms 596 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 2 ms 520 KB Output is correct
5 Correct 2 ms 596 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 2 ms 596 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 206 ms 26680 KB Output is correct
10 Correct 206 ms 26632 KB Output is correct
11 Correct 133 ms 26620 KB Output is correct
12 Correct 192 ms 26660 KB Output is correct
13 Correct 123 ms 26124 KB Output is correct
14 Correct 136 ms 26556 KB Output is correct
15 Correct 185 ms 25912 KB Output is correct
16 Correct 148 ms 26612 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 25792 KB Output is correct
2 Correct 149 ms 27704 KB Output is correct
3 Correct 146 ms 27568 KB Output is correct
4 Correct 146 ms 25516 KB Output is correct
5 Correct 143 ms 26724 KB Output is correct
6 Correct 144 ms 25916 KB Output is correct
7 Correct 150 ms 26876 KB Output is correct
8 Correct 156 ms 25512 KB Output is correct
9 Correct 169 ms 25496 KB Output is correct
10 Correct 147 ms 27872 KB Output is correct
11 Correct 144 ms 26308 KB Output is correct
12 Correct 143 ms 27356 KB Output is correct
13 Correct 137 ms 25500 KB Output is correct
14 Correct 144 ms 27420 KB Output is correct
15 Correct 153 ms 27296 KB Output is correct
16 Correct 148 ms 25536 KB Output is correct
17 Correct 151 ms 26776 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 25792 KB Output is correct
2 Correct 149 ms 27704 KB Output is correct
3 Correct 146 ms 27568 KB Output is correct
4 Correct 146 ms 25516 KB Output is correct
5 Correct 143 ms 26724 KB Output is correct
6 Correct 144 ms 25916 KB Output is correct
7 Correct 150 ms 26876 KB Output is correct
8 Correct 156 ms 25512 KB Output is correct
9 Correct 169 ms 25496 KB Output is correct
10 Correct 147 ms 27872 KB Output is correct
11 Correct 144 ms 26308 KB Output is correct
12 Correct 143 ms 27356 KB Output is correct
13 Correct 137 ms 25500 KB Output is correct
14 Correct 144 ms 27420 KB Output is correct
15 Correct 153 ms 27296 KB Output is correct
16 Correct 148 ms 25536 KB Output is correct
17 Correct 151 ms 26776 KB Output is correct
18 Correct 210 ms 25824 KB Output is correct
19 Correct 308 ms 29540 KB Output is correct
20 Correct 150 ms 29536 KB Output is correct
21 Correct 170 ms 27608 KB Output is correct
22 Correct 177 ms 27860 KB Output is correct
23 Correct 181 ms 27696 KB Output is correct
24 Correct 221 ms 28216 KB Output is correct
25 Correct 138 ms 27424 KB Output is correct
26 Correct 215 ms 27320 KB Output is correct
27 Correct 229 ms 29964 KB Output is correct
28 Correct 172 ms 27828 KB Output is correct
29 Correct 196 ms 29204 KB Output is correct
30 Correct 179 ms 27304 KB Output is correct
31 Correct 171 ms 29300 KB Output is correct
32 Correct 153 ms 29164 KB Output is correct
33 Correct 210 ms 26976 KB Output is correct
34 Correct 179 ms 28732 KB Output is correct