oj.uz

Submission #1105082

# Submission time Handle Problem Language Result Execution time Memory
1105082 2024-10-25T09:58:51 Z siewjh Distributing Candies (IOI21_candies) C++17
29 / 100
 430 ms 53848 KB 
#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef tuple<ll, ll, ll> iii;
const int MAXN = 200005;
const ll inf = 1e18;
struct node{
	int s, e, m; ll mx, mn, lazy;
	node *l, *r;
	node (int _s, int _e){
		s = _s, e = _e, m = (s + e) >> 1; mx = mn = lazy = 0;
		if (s != e){
			l = new node(s, m); r = new node(m + 1, e);
		}
	}
	void push(ll v){
		mx += v; mn += v;
		lazy += v;
	}
	void propo(){
		if (s == e) return;
		if (lazy != 0){
			l->push(lazy); r->push(lazy);
			lazy = 0;
		}
	}
	void update(int x, int y, ll v){
		if (x == s && y == e){
			push(v); return;
		}
		propo();
		if (y <= m) l->update(x, y, v);
		else if (x > m) r->update(x, y, v);
		else{
			l->update(x, m, v); r->update(m + 1, y, v);
		}
		mx = max(l->mx, r->mx); mn = min(l->mn, r->mn);
	}
	ll query(int x){
		if (s == e) return mx;
		propo();
		if (x <= m) return l->query(x);
		else return r->query(x);
	}
	iii find(ll omx, ll omn, ll range){
		if (s == e) return {s, omx, omn};
		ll nmx = max(omx, r->mx), nmn = min(omn, r->mn);
		if (nmx - nmn <= range) return l->find(nmx, nmn, range);
		else return r->find(omx, omn, range);
	}
};
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v){
	int nums = c.size(), queries = l.size();
	vector<vector<int>> rsv(nums), rev(nums);
	for (int q = 0; q < queries; q++){
		rsv[l[q]].push_back(q);
		rev[r[q]].push_back(q);
	}
	node *root = new node(-2, queries - 1);
	root->update(-2, -2, inf);
	vector<int> ans(nums);
	for (int i = 0; i < nums; i++){
		for (int q : rsv[i]) root->update(q, queries - 1, v[q]);
		ll fid, mx, mn; tie(fid, mx, mn) = root->find(-inf, inf, c[i]);
		ll fv = root->query(fid), ev = root->query(queries - 1);
		if (fv > mx) ans[i] = ev - mn;
		else ans[i] = c[i] - (mx - ev);
		for (int q : rev[i]) root->update(q, queries - 1, -v[q]);
	}
	return ans;
}

Subtask #1
0 / 3.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Incorrect 220 ms 34668 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 112 ms 34244 KB Output is correct
4 Correct 52 ms 13648 KB Output is correct
5 Correct 180 ms 46772 KB Output is correct
6 Correct 179 ms 47796 KB Output is correct
7 Correct 170 ms 48052 KB Output is correct
8 Correct 159 ms 46800 KB Output is correct
9 Correct 158 ms 48328 KB Output is correct

Subtask #5
0 / 33.0

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