oj.uz

Submission #1043551

# Submission time Handle Problem Language Result Execution time Memory
1043551 2024-08-04T11:02:52 Z AmirAli_H1 Distributing Candies (IOI21_candies) C++17
38 / 100
 263 ms 44400 KB 
// In the name of Allah

#include <bits/stdc++.h>
#include "candies.h"
using namespace std;

typedef		long long				ll;
typedef		long double				ld;
typedef		pair<int, int>			pii;
typedef		pair<ll, ll>			pll;

#define		endl					'\n'
#define		sep						' '
#define		F						first
#define		S						second
#define		all(x)					(x).begin(),(x).end()
#define		len(x)					((ll) (x).size())
#define		pb						push_back
#define		Mp						make_pair

const int maxn = 2e5 + 4;
const ll oo = 1e18 + 4;

struct node {
	ll val;
	pll lazym; ll lazys;
};

int n, q;
ll A[maxn]; pair<pii, ll> Q[maxn];
ll val[maxn]; vector<int> ans;
node t[4 * maxn];

void shift(int v, int tl, int tr) {
	ll x1 = t[v].lazym.F, x2 = t[v].lazym.S, R = t[v].lazys;
	t[v].lazym = Mp(oo, -oo); t[v].lazys = 0;
	if (tr - tl == 1) return ;
	
	for (int u : {2 * v + 1, 2 * v + 2}) {
		t[u].val = min(t[u].val, x1); t[u].val = max(t[u].val, x2);
		t[u].val += R;
		
		t[u].lazym.F = min(t[u].lazym.F, x1 - t[u].lazys);
		t[u].lazym.S = max(t[u].lazym.S, x2 - t[u].lazys);
		if (t[u].lazym.S > t[u].lazym.F) {
			if (t[u].lazym.S == x2 - t[u].lazys) t[u].lazym.F = t[u].lazym.S;
			else t[u].lazym.S = t[u].lazym.F;
		}
		t[u].lazys += R;
	}
}

void build(int v, int tl, int tr) {
	t[v].val = 0;
	t[v].lazym = Mp(oo, -oo); t[v].lazys = 0;
	if (tr - tl == 1) return ;
	int mid = (tl + tr) / 2;
	build(2 * v + 1, tl, mid); build(2 * v + 2, mid, tr);
}

void add_val(int v, int tl, int tr, int l, int r, ll x) {
	l = max(l, tl); r = min(r, tr);
	if (l >= tr || r <= tl) return ;
	shift(v, tl, tr);
	if (l == tl && r == tr) {
		t[v].val += x; t[v].lazys += x;
		return ;
	}
	int mid = (tl + tr) / 2;
	add_val(2 * v + 1, tl, mid, l, r, x); add_val(2 * v + 2, mid, tr, l, r, x);
}

void set_min(int v, int tl, int tr, int l, int r, ll x) {
	l = max(l, tl); r = min(r, tr);
	if (l >= tr || r <= tl) return ;
	shift(v, tl, tr);
	if (l == tl && r == tr) {
		t[v].val = min(t[v].val, x);
		t[v].lazym.F = min(t[v].lazym.F, x);
		return ;
	}
	int mid = (tl + tr) / 2;
	set_min(2 * v + 1, tl, mid, l, r, x); set_min(2 * v + 2, mid, tr, l, r, x);
}

void set_max(int v, int tl, int tr, int l, int r, ll x) {
	l = max(l, tl); r = min(r, tr);
	if (l >= tr || r <= tl) return ;
	shift(v, tl, tr);
	if (l == tl && r == tr) {
		t[v].val = max(t[v].val, x);
		t[v].lazym.S = max(t[v].lazym.S, x);
		return ;
	}
	int mid = (tl + tr) / 2;
	set_max(2 * v + 1, tl, mid, l, r, x); set_max(2 * v + 2, mid, tr, l, r, x);
}

void get_res(int v, int tl, int tr) {
	shift(v, tl, tr);
	if (tr - tl == 1) {
		val[tl] = max(0ll, min(A[tl], t[v].val));
		return ;
	}
	int mid = (tl + tr) / 2;
	get_res(2 * v + 1, tl, mid); get_res(2 * v + 2, mid, tr);
}

void solve1() {
	for (int i = 0; i < q; i++) {
		int l = Q[i].F.F, r = Q[i].F.S, x = Q[i].S;
		for (int j = l; j < r; j++) {
			val[j] += x;
			val[j] = (val[j] >= 0) ? val[j] : 0;
			val[j] = (val[j] <= A[j]) ? val[j] : A[j];
		}
	}
}

void solve2() {
	int mx = *max_element(A, A + n);
	build(0, 0, n);
	for (int i = 0; i < q; i++) {
		int l = Q[i].F.F, r = Q[i].F.S, x = Q[i].S;
		add_val(0, 0, n, l, r, x);
		if (x < 0) set_max(0, 0, n, 0, n, 0);
		else set_min(0, 0, n, 0, n, mx);
	}
	get_res(0, 0, n);
}

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
	n = len(c); q = len(l);
	for (int i = 0; i < n; i++) A[i] = c[i];
	for (int i = 0; i < q; i++) Q[i] = Mp(Mp(l[i], r[i] + 1), v[i]);
	fill(val, val + n, 0);
	
	if (n <= 2000 && q <= 2000) solve1();
	else solve2();
	
	ans.clear(); ans.resize(n);
	for (int i = 0; i < n; i++) ans[i] = val[i];
	return ans;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 29276 KB Output is correct
2 Correct 3 ms 29276 KB Output is correct
3 Correct 4 ms 29276 KB Output is correct
4 Correct 4 ms 29276 KB Output is correct
5 Correct 4 ms 29352 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 44400 KB Output is correct
2 Correct 191 ms 39760 KB Output is correct
3 Correct 182 ms 39504 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 29272 KB Output is correct
2 Correct 120 ms 37192 KB Output is correct
3 Correct 34 ms 34880 KB Output is correct
4 Correct 253 ms 42048 KB Output is correct
5 Correct 246 ms 39340 KB Output is correct
6 Correct 263 ms 39400 KB Output is correct
7 Correct 242 ms 39532 KB Output is correct

Subtask #4
0 / 29.0

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

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 29276 KB Output is correct
2 Correct 3 ms 29276 KB Output is correct
3 Correct 4 ms 29276 KB Output is correct
4 Correct 4 ms 29276 KB Output is correct
5 Correct 4 ms 29352 KB Output is correct
6 Correct 181 ms 44400 KB Output is correct
7 Correct 191 ms 39760 KB Output is correct
8 Correct 182 ms 39504 KB Output is correct
9 Correct 3 ms 29272 KB Output is correct
10 Correct 120 ms 37192 KB Output is correct
11 Correct 34 ms 34880 KB Output is correct
12 Correct 253 ms 42048 KB Output is correct
13 Correct 246 ms 39340 KB Output is correct
14 Correct 263 ms 39400 KB Output is correct
15 Correct 242 ms 39532 KB Output is correct
16 Correct 3 ms 29276 KB Output is correct
17 Correct 3 ms 29276 KB Output is correct
18 Incorrect 37 ms 37208 KB Output isn't correct
19 Halted 0 ms 0 KB -