oj.uz

Submission #1043503

# Submission time Handle Problem Language Result Execution time Memory
1043503 2024-08-04T10:15:53 Z AmirAli_H1 Distributing Candies (IOI21_candies) C++17
11 / 100
 226 ms 38776 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, int> Q[maxn];
ll val[maxn]; vector<int> ans;
node t[4 * maxn];

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 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) t[u].lazym.F = t[u].lazym.S;
		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);
		if (t[v].lazym.S >= t[v].lazym.F) t[v].lazym.F = t[v].lazym.S;
		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);
		if (t[v].lazym.S >= t[v].lazym.F) t[v].lazym.F = t[v].lazym.S;
		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 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);
		set_max(0, 0, n, 0, n, 0); 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 27228 KB Output is correct
2 Correct 3 ms 27228 KB Output is correct
3 Correct 3 ms 27228 KB Output is correct
4 Correct 3 ms 27228 KB Output is correct
5 Correct 6 ms 27228 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 38776 KB Output is correct
2 Correct 226 ms 38616 KB Output is correct
3 Correct 206 ms 38740 KB Output is correct

Subtask #3
0 / 27.0

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

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 27480 KB Output is correct
2 Correct 3 ms 27224 KB Output is correct
3 Incorrect 58 ms 34008 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 27228 KB Output is correct
2 Correct 3 ms 27228 KB Output is correct
3 Correct 3 ms 27228 KB Output is correct
4 Correct 3 ms 27228 KB Output is correct
5 Correct 6 ms 27228 KB Output is correct
6 Correct 180 ms 38776 KB Output is correct
7 Correct 226 ms 38616 KB Output is correct
8 Correct 206 ms 38740 KB Output is correct
9 Correct 3 ms 27224 KB Output is correct
10 Incorrect 121 ms 34132 KB Output isn't correct
11 Halted 0 ms 0 KB -