oj.uz

Submission #483889

# Submission time Handle Problem Language Result Execution time Memory
483889 2021-11-01T08:34:12 Z 8e7 Distributing Candies (IOI21_candies) C++17
100 / 100
 617 ms 45668 KB 
//Challenge: Accepted
#include "candies.h"
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
using namespace std;
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ...b) {
	cout << a << " ", debug(b ...);
};
template<class T> void pary (T l, T r) {
	while (l!= r) cout << *l << " ", l++;
	cout << endl;
};
#define ll long long
#define maxn 200005
#define pii pair<ll, ll>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
const ll inf = 1LL<<60;
struct segtree{
	ll ma[4 * maxn], mi[4 * maxn], tag[4 * maxn];	
	int ama[4 * maxn], ami[4 * maxn];
	void init(int cur, int l, int r) {
		if (r <= l) return;
		if (r - l == 1) {
			ama[cur] = ami[cur] = l;
			return;
		}
		int mid = (l + r) / 2;
		init(cur * 2, l, mid), init(cur * 2 + 1, mid, r);
		ama[cur] = ami[cur] = l;
	}
	void push(int cur, int l, int r) {
		if (!tag[cur]) return;
		ma[cur] += tag[cur], mi[cur] += tag[cur];
		if (r - l > 1) tag[cur * 2] += tag[cur], tag[cur * 2 + 1] += tag[cur];
		tag[cur] = 0;		
	}
	void pull(int cur, int l, int r) {
		push(cur, l, r);
		if (r - l < 2) return;
		int m = (l + r) / 2;
		push(cur * 2, l, m), push(cur * 2 + 1, m, r);	
		if (ma[cur*2] > ma[cur*2+1]) ma[cur] = ma[cur*2], ama[cur] = ama[cur*2];
		else ma[cur] = ma[cur*2+1], ama[cur] = ama[cur*2+1];
		if (mi[cur*2] < mi[cur*2+1]) mi[cur] = mi[cur*2], ami[cur] = ami[cur*2];
		else mi[cur] = mi[cur*2+1], ami[cur] = ami[cur*2+1];
	}
	void modify(int cur, int l, int r, int ql, int qr, ll val) {
		if (r <= l || ql >= r || qr <= l) return;
		push(cur, l, r);
		if (ql <= l && qr >= r) {
			tag[cur] += val;return;
		}
		int mid = (l + r) / 2;
		modify(cur * 2, l, mid, ql, qr, val), modify(cur*2+1, mid, r, ql, qr, val);
		pull(cur, l, r);
		//debug("seg", l, r, ma[cur], mi[cur]);
	}
	pii search(int cur, int l, int r,ll big, ll small,ll c) { //maximum id 
		push(cur, l, r);
		if (max(big, ma[cur]) - min(small, mi[cur]) <= c) {
			//debug("f", max(big, ma[cur]), min(small, mi[cur]), c, l, r);
			return make_pair(-1, 0);
		}
		if (r - l == 1) {
			return {l, (ma[cur] - small > c ? 0 : c)};
		}
		int m = (l + r) / 2;
		pull(cur, l, r);
		if (max(ma[cur*2+1], big) - min(small, mi[cur*2+1]) > c) {
			//debug("rig", m, r);
			return search(cur*2+1, m, r, big, small, c);
		} else {
			return search(cur*2, l, m, max(ma[cur*2+1], big), min(small, mi[cur*2+1]), c);
		}
	}
	pii getval(int cur, int l, int r, int ql, int qr) { //returns max, min of segment
		if (r <= l || ql >= r || qr <= l) return {-inf, inf};
		push(cur, l, r);
		if (ql <= l && qr >= r) {
			pull(cur, l, r);
			return {ma[cur], mi[cur]};
		}
		int m = (l + r) / 2;
		pii lef = getval(cur * 2, l, m, ql, qr), rig = getval(cur*2+1, m, r, ql, qr);
		return make_pair(max(lef.ff, rig.ff), min(lef.ss, rig.ss));
	}
}seg;
vector<pii> ch[maxn];
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
    int n = c.size(), q = v.size();
	vector<int> ret(n, 0);
	for (int i = 0;i < q;i++) {
		ch[l[i]].push_back({v[i], i+1});
		ch[r[i] + 1].push_back({-v[i], i+1});
	}
	q++;
	seg.init(1, 0, q);	
	for (int i = 0;i < n;i++) {
		for (auto p:ch[i]) {
			//debug("mod", p.ss, q, p.ff);
			seg.modify(1, 0, q, p.ss, q, p.ff);	
		}
		pii p = seg.search(1, 0, q, -inf, inf, c[i]), last = seg.getval(1, 0, q, q-1, q);
		//debug(p.ff, p.ss);
		if (p.ff == -1) {
			pii all = seg.getval(1, 0, q, 0, q);
			ret[i] = last.ff - all.ss;
			//debug(0, last.ff, all.ss);
		} else {
			pii rem = seg.getval(1, 0, q, p.ff+1, q);
			if (p.ss == 0) ret[i] = last.ff - rem.ss;
			else ret[i] = c[i] - (rem.ff - last.ff);
			//debug(1, last.ff, rem.ff, rem.ss, p.ss);
		}
		//debug(i, ret[i]);
	}
	return ret;
}
/*
6
2 12 11 7 1 19
4
4 5 14
0 4 14
1 4 10
5 5 -18
*/

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4940 KB Output is correct
2 Correct 2 ms 4940 KB Output is correct
3 Correct 4 ms 5196 KB Output is correct
4 Correct 4 ms 5324 KB Output is correct
5 Correct 5 ms 5324 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 487 ms 38944 KB Output is correct
2 Correct 484 ms 43012 KB Output is correct
3 Correct 474 ms 42820 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 252 ms 35008 KB Output is correct
3 Correct 111 ms 11000 KB Output is correct
4 Correct 513 ms 44880 KB Output is correct
5 Correct 548 ms 45276 KB Output is correct
6 Correct 484 ms 45668 KB Output is correct
7 Correct 474 ms 44976 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 105 ms 32464 KB Output is correct
4 Correct 103 ms 7752 KB Output is correct
5 Correct 227 ms 34972 KB Output is correct
6 Correct 236 ms 34924 KB Output is correct
7 Correct 255 ms 35060 KB Output is correct
8 Correct 222 ms 34976 KB Output is correct
9 Correct 273 ms 34916 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4940 KB Output is correct
2 Correct 2 ms 4940 KB Output is correct
3 Correct 4 ms 5196 KB Output is correct
4 Correct 4 ms 5324 KB Output is correct
5 Correct 5 ms 5324 KB Output is correct
6 Correct 487 ms 38944 KB Output is correct
7 Correct 484 ms 43012 KB Output is correct
8 Correct 474 ms 42820 KB Output is correct
9 Correct 3 ms 4940 KB Output is correct
10 Correct 252 ms 35008 KB Output is correct
11 Correct 111 ms 11000 KB Output is correct
12 Correct 513 ms 44880 KB Output is correct
13 Correct 548 ms 45276 KB Output is correct
14 Correct 484 ms 45668 KB Output is correct
15 Correct 474 ms 44976 KB Output is correct
16 Correct 3 ms 4940 KB Output is correct
17 Correct 3 ms 4940 KB Output is correct
18 Correct 105 ms 32464 KB Output is correct
19 Correct 103 ms 7752 KB Output is correct
20 Correct 227 ms 34972 KB Output is correct
21 Correct 236 ms 34924 KB Output is correct
22 Correct 255 ms 35060 KB Output is correct
23 Correct 222 ms 34976 KB Output is correct
24 Correct 273 ms 34916 KB Output is correct
25 Correct 3 ms 5000 KB Output is correct
26 Correct 89 ms 8840 KB Output is correct
27 Correct 253 ms 37564 KB Output is correct
28 Correct 507 ms 43588 KB Output is correct
29 Correct 503 ms 43788 KB Output is correct
30 Correct 510 ms 44040 KB Output is correct
31 Correct 520 ms 44296 KB Output is correct
32 Correct 617 ms 44476 KB Output is correct