oj.uz

Submission #791272

# Submission time Handle Problem Language Result Execution time Memory
791272 2023-07-23T21:13:21 Z IvanJ Distributing Candies (IOI21_candies) C++17
100 / 100
 1823 ms 42212 KB 
#include "candies.h"
#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 = 2e5 + 5, inf = 1e9;
const ll INF = 1e18;

struct Data {
	ll lo, hi;
	int min_idx;
};

Data merge(Data A, Data B) {
	Data ret = {INF, -INF, -1};
	ret.lo = min(A.lo, B.lo);
	ret.hi = max(A.hi, B.hi);
	ret.min_idx = A.min_idx;
	if(ret.lo == B.lo)
		ret.min_idx = B.min_idx;
	return ret;
}

struct Seg {
	int pot = 1, n;
	vector<Data> T;
	vector<ll> L;
	void init(int _n) {
		n = _n;
		while(pot < n) pot <<= 1;
		for(int i = 0;i < (pot << 1);i++) T.pb({0, 0, -1}), L.pb(0);
		for(int i = 0;i < n;i++) T[i + pot].min_idx = i;
		for(int i = pot - 1;i > 0;i--) 
			T[i] = merge(T[i * 2], T[i * 2 + 1]);
	}
	
	void prop(int x) {
		if(L[x] == 0) return;
		T[x].lo += L[x];
		T[x].hi += L[x];
		if(x < pot) 
			L[x * 2] += L[x], L[x * 2 + 1] += L[x];
		L[x] = 0;
	}
	
	void add(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) {
			L[x] += v;
			prop(x);
			return;
		} 
		int mid = (lo + hi) / 2;
		add(x * 2, lo, mid, a, b, v);
		add(x * 2 + 1, mid + 1, hi, a, b, v);
		T[x] = merge(T[x * 2], T[x * 2 + 1]);
	}
	
	void update(int x, ll v) {add(1, 0, pot - 1, x, n - 1, v);}
	
	Data get_min(int x, int lo, int hi, int a, int b) {
		prop(x);
		if(hi < a || b < lo) return {INF, -INF, -1};
		if(a <= lo && hi <= b) return T[x];
		int mid = (lo + hi) / 2;
		Data l = get_min(x * 2, lo, mid, a, b);
		Data r = get_min(x * 2 + 1, mid + 1, hi, a, b);
		if(l.min_idx == -1) return r;
		if(r.min_idx == -1) return l;
		if(l.lo < r.lo) return l;
		return r;
	}
	
	int query(int lo, int hi) {return get_min(1, 0, pot - 1, lo, hi).min_idx;}
	
	Data get_range(int x, int lo, int hi, int a, int b) {
		prop(x);
		if(hi < a || b < lo) return {INF, -INF, -1};
		if(a <= lo && hi <= b) return T[x];
		int mid = (lo + hi) / 2;
		Data l = get_range(x * 2, lo, mid, a, b);
		Data r = get_range(x * 2 + 1, mid + 1, hi, a, b);
		return merge(l, r);
	}
	
	Data query2(int lo, int hi) {return get_range(1, 0, pot - 1, lo, hi);}
	
	int solve(ll c) {
		int lo = 0, hi = n - 1, ans = -1;
		while(lo <= hi) {
			int mid = (lo + hi) / 2;
			Data D = query2(mid, n - 1);
			//cout << mid << " -> " << D.lo << " " << D.hi << " mid\n";
			if(D.hi - D.lo < c) ans = mid, hi = mid - 1;
			else lo = mid + 1;
		}
		return ans;
	}
	
	ll get_val(int x, int lo, int hi, int X) {
		prop(x);
		if(lo == hi) return T[x].lo;
		int mid = (lo + hi) / 2;
		if(X <= mid) return get_val(x * 2, lo, mid, X);
		return get_val(x * 2 + 1, mid + 1, hi, X);
	}
	
	ll get(int x) {return get_val(1, 0, pot - 1, x);}
};

int n, q;
vector<ii> sweep[maxn];
Seg S;

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
    n = (int)c.size();
    q = (int)l.size();
    S.init(q + 2);
    vector<int> ans(n, 0);
    
    for(int i = 0;i < q;i++) 
		sweep[l[i]].pb({v[i], i + 2}), sweep[r[i] + 1].pb({-v[i], i + 2});
	
	S.update(0, inf);
	S.update(1, -inf);
	for(int i = 0;i < n;i++) {
		for(ii p : sweep[i]) 
			S.update(p.y, p.x);
		
		//for(int j = 0;j < q + 2;j++) 
		//	cout << S.get(j) << " ";
		//cout << "\n";
		
		int t_max = S.solve(c[i]);
		//cout << t_max << " tmax\n";
		ll h1 = S.get(t_max - 1), h2 = S.get(t_max);
		Data D = S.query2(t_max, q + 1);
		ll X = 0;
		X = c[i] - (D.hi - D.lo);
		if(h1 > h2) X = 0;
		int mini = S.query(t_max, q + 1);
		
		//cout << S.get(mini) << " " << S.get(q + 1) << " " << X << " X\n";
		ans[i] = S.get(q + 1) - S.get(mini) + X;
		//cout << "\n\n";
	}
    return ans;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 4 ms 5272 KB Output is correct
4 Correct 4 ms 5204 KB Output is correct
5 Correct 12 ms 5200 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1687 ms 35628 KB Output is correct
2 Correct 1768 ms 39572 KB Output is correct
3 Correct 1808 ms 39420 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 297 ms 30800 KB Output is correct
3 Correct 556 ms 8796 KB Output is correct
4 Correct 1776 ms 35636 KB Output is correct
5 Correct 1823 ms 41832 KB Output is correct
6 Correct 1565 ms 42212 KB Output is correct
7 Correct 1549 ms 41680 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 145 ms 31924 KB Output is correct
4 Correct 452 ms 7824 KB Output is correct
5 Correct 1382 ms 34532 KB Output is correct
6 Correct 1304 ms 38588 KB Output is correct
7 Correct 1172 ms 39264 KB Output is correct
8 Correct 1389 ms 37816 KB Output is correct
9 Correct 1506 ms 39292 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 4 ms 5272 KB Output is correct
4 Correct 4 ms 5204 KB Output is correct
5 Correct 12 ms 5200 KB Output is correct
6 Correct 1687 ms 35628 KB Output is correct
7 Correct 1768 ms 39572 KB Output is correct
8 Correct 1808 ms 39420 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 297 ms 30800 KB Output is correct
11 Correct 556 ms 8796 KB Output is correct
12 Correct 1776 ms 35636 KB Output is correct
13 Correct 1823 ms 41832 KB Output is correct
14 Correct 1565 ms 42212 KB Output is correct
15 Correct 1549 ms 41680 KB Output is correct
16 Correct 2 ms 4948 KB Output is correct
17 Correct 3 ms 4948 KB Output is correct
18 Correct 145 ms 31924 KB Output is correct
19 Correct 452 ms 7824 KB Output is correct
20 Correct 1382 ms 34532 KB Output is correct
21 Correct 1304 ms 38588 KB Output is correct
22 Correct 1172 ms 39264 KB Output is correct
23 Correct 1389 ms 37816 KB Output is correct
24 Correct 1506 ms 39292 KB Output is correct
25 Correct 2 ms 4948 KB Output is correct
26 Correct 492 ms 8860 KB Output is correct
27 Correct 271 ms 33220 KB Output is correct
28 Correct 1705 ms 40068 KB Output is correct
29 Correct 1665 ms 40548 KB Output is correct
30 Correct 1632 ms 40660 KB Output is correct
31 Correct 1591 ms 40804 KB Output is correct
32 Correct 1525 ms 41040 KB Output is correct