oj.uz

Submission #621302

# Submission time Handle Problem Language Result Execution time Memory
621302 2022-08-03T17:03:11 Z M_W Distributing Candies (IOI21_candies) C++17
100 / 100
 1102 ms 31160 KB 
#include <bits/stdc++.h>
#define ar array<int, 3>
#define ii pair<long long, long long>
using namespace std;
int N, Q;
ii t[200002 << 2];
long long lazy[200002 << 2];

void push(int v){
	if(lazy[v] == 0) return;
	t[v * 2].first += lazy[v];
	t[v * 2 + 1].first += lazy[v];
	
	t[v * 2].second += lazy[v];
	t[v * 2 + 1].second += lazy[v];
	
	lazy[v * 2] += lazy[v];
	lazy[v * 2 + 1] += lazy[v];
	lazy[v] = 0;
	
	return;
}

void ins(int v, int tl, int tr, int l, int r, int val){
	if(l > r) return;
	if(tl == l && tr == r){
		t[v].first += val * 1ll; t[v].second += val * 1ll;
		lazy[v] += val * 1ll;
		return;
	}
	push(v);
	int tm = (tl + tr) >> 1;
	
	ins(v * 2, tl, tm, l, min(r, tm), val);
	ins(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r, val);
	
	t[v].first = max(t[v * 2].first, t[v * 2 + 1].first);
	t[v].second = min(t[v * 2].second, t[v * 2 + 1].second);
}

ii query(int v, int tl, int tr, int l, int r){
	if(l > r) return {LLONG_MIN, LLONG_MAX};
	if(tl == l && tr == r) return t[v];
	push(v);
	int tm = (tl + tr) >> 1;
	
	ii ll = query(v * 2, tl, tm, l, min(r, tm));
	ii rr = query(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r);
	
	ii res = ll; res.first = max(res.first, rr.first); res.second = min(res.second, rr.second);
	return res;
}

vector<int> distribute_candies(vector<int> C, vector<int> L, vector<int> R, vector<int> V){
	N = C.size(); Q = L.size(); vector<int> ans(200002);
	priority_queue<ar, vector<ar>, greater<ar>> pq;
	for(int i = 0; i < Q; i++){
		pq.push({L[i], V[i], i + 1});
		pq.push({R[i] + 1, -V[i], i + 1});
	}
	
	for(int i = 0; i < N; i++){
		while(!pq.empty() && pq.top()[0] == i){
			ins(1, 0, Q, pq.top()[2], Q, pq.top()[1]);
			pq.pop();
		}
		int l = 0, r = Q;
		while(l < r){
			int mid = (l + r) >> 1;
			ii res = query(1, 0, Q, mid, Q);
			long long diff = res.first - res.second;
			
			if(diff > C[i]) l = mid + 1;
			else r = mid;
		}

		ii res = query(1, 0, Q, l, Q);
		long long last = (query(1, 0, Q, Q, Q)).first;
		
		if(l <= 0) ans[i] = last - res.second;
		else{
			long long bef = (query(1, 0, Q, l - 1, l - 1)).first;

			if(bef < res.first) ans[i] = C[i] - (res.first - last); // Hit top
			else ans[i] = last - res.second; // Hit bottom
		}
	}
	ans.resize(N);
	return ans;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1108 KB Output is correct
2 Correct 1 ms 1108 KB Output is correct
3 Correct 2 ms 1236 KB Output is correct
4 Correct 3 ms 1364 KB Output is correct
5 Correct 6 ms 1364 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1102 ms 24580 KB Output is correct
2 Correct 1014 ms 24484 KB Output is correct
3 Correct 1012 ms 24412 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1108 KB Output is correct
2 Correct 338 ms 25964 KB Output is correct
3 Correct 328 ms 6212 KB Output is correct
4 Correct 995 ms 30368 KB Output is correct
5 Correct 973 ms 30744 KB Output is correct
6 Correct 1045 ms 31160 KB Output is correct
7 Correct 955 ms 30532 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1108 KB Output is correct
2 Correct 1 ms 1108 KB Output is correct
3 Correct 217 ms 22884 KB Output is correct
4 Correct 259 ms 3048 KB Output is correct
5 Correct 805 ms 24732 KB Output is correct
6 Correct 803 ms 24928 KB Output is correct
7 Correct 736 ms 24900 KB Output is correct
8 Correct 747 ms 24876 KB Output is correct
9 Correct 766 ms 25880 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1108 KB Output is correct
2 Correct 1 ms 1108 KB Output is correct
3 Correct 2 ms 1236 KB Output is correct
4 Correct 3 ms 1364 KB Output is correct
5 Correct 6 ms 1364 KB Output is correct
6 Correct 1102 ms 24580 KB Output is correct
7 Correct 1014 ms 24484 KB Output is correct
8 Correct 1012 ms 24412 KB Output is correct
9 Correct 1 ms 1108 KB Output is correct
10 Correct 338 ms 25964 KB Output is correct
11 Correct 328 ms 6212 KB Output is correct
12 Correct 995 ms 30368 KB Output is correct
13 Correct 973 ms 30744 KB Output is correct
14 Correct 1045 ms 31160 KB Output is correct
15 Correct 955 ms 30532 KB Output is correct
16 Correct 1 ms 1108 KB Output is correct
17 Correct 1 ms 1108 KB Output is correct
18 Correct 217 ms 22884 KB Output is correct
19 Correct 259 ms 3048 KB Output is correct
20 Correct 805 ms 24732 KB Output is correct
21 Correct 803 ms 24928 KB Output is correct
22 Correct 736 ms 24900 KB Output is correct
23 Correct 747 ms 24876 KB Output is correct
24 Correct 766 ms 25880 KB Output is correct
25 Correct 1 ms 1076 KB Output is correct
26 Correct 291 ms 4112 KB Output is correct
27 Correct 348 ms 25476 KB Output is correct
28 Correct 936 ms 29128 KB Output is correct
29 Correct 952 ms 29352 KB Output is correct
30 Correct 1063 ms 29656 KB Output is correct
31 Correct 968 ms 29724 KB Output is correct
32 Correct 938 ms 30096 KB Output is correct