oj.uz

Submission #621297

# Submission time Handle Problem Language Result Execution time Memory
621297 2022-08-03T16:50:08 Z M_W Distributing Candies (IOI21_candies) C++17
8 / 100
 1162 ms 28592 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;
		}
		if(l <= 0) ans[i] = int((query(1, 0, Q, Q, Q)).first);
		else{
			ii res = query(1, 0, Q, l, Q);
			long long bef = (query(1, 0, Q, l - 1, l - 1)).first;
			long long last = (query(1, 0, Q, Q, Q)).first;
			
			if(bef < res.first) ans[i] = C[i] - (res.first - last); // Hit top
			else ans[i] = last - res.second; // Hit bottom
		}
		ans[i] = max(ans[i], 0);
	}
	ans.resize(N);
	return ans;
}

Subtask #1
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 Incorrect 3 ms 1364 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1109 ms 24408 KB Output is correct
2 Correct 1162 ms 28592 KB Output is correct
3 Correct 1060 ms 28304 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1108 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
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 Incorrect 242 ms 23148 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
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 Incorrect 3 ms 1364 KB Output isn't correct
4 Halted 0 ms 0 KB -