oj.uz

Submission #808176

# Submission time Handle Problem Language Result Execution time Memory
808176 2023-08-05T04:58:42 Z khshg Distributing Candies (IOI21_candies) C++17
27 / 100
 478 ms 30460 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long

// max -> x
// if mn <= mx < x ; add (x - mx)
// if x <= mn ; do nothing end
// assert(mn < x <= mx) go down

// min -> x
// if x < mn <= mx; add (x - mn)
// if mn <= mx <= x do nothing end
// assert(mn <= x < mx) go down

const int maxn =  200010;

struct node {
	ll mn, mx;
	ll sum, lazy;
}st[4 * maxn];

#define tm ((tl + tr) >> 1)
#define lv ((v << 1) | 1)
#define rv (lv + 1)
void push(int v, int tl, int tr) {
	if(!st[v].lazy) return;
	st[lv].lazy += st[v].lazy;
	st[lv].sum += 1LL * (tm - tl + 1) * st[v].lazy;
	st[lv].mn += st[v].lazy;
	st[lv].mx += st[v].lazy;
	st[rv].lazy += st[v].lazy;
	st[rv].sum += 1LL * (tr - tm) * st[v].lazy;
	st[rv].mn += st[v].lazy;
	st[rv].mx += st[v].lazy;
	st[v].lazy = 0;
}

void pull(int v) {
	st[v].sum = st[lv].sum + st[rv].sum;
	st[v].mn = min(st[lv].mn, st[rv].mn);
	st[v].mx = max(st[lv].mx, st[rv].mx);
}

void add(int v, int tl, int tr, int l, int r, int val) {
	if(tr < l || r < tl) return;
	if(l <= tl && tr <= r) {
		st[v].lazy += val;
		st[v].sum += 1LL * (tr - tl + 1) * val;
		st[v].mn += val;
		st[v].mx += val;
		return;
	}
	push(v, tl, tr);
	add(lv, tl, tm, l, r, val);
	add(rv, tm + 1, tr, l, r, val);
	pull(v);
}

void chmax(int v, int tl, int tr, int l, int r, int val) {
	if(tl > tr) return;
	if(tr < l || r < tl || st[v].mn >= val) return;
	if(l <= tl && tr <= r) {
		if(st[v].mx < val) {
			ll d = val - st[v].mx;
			st[v].lazy += d;
			st[v].sum += 1LL * (tr - tl + 1) * d;
			st[v].mn += d;
			st[v].mx += d;
		}
		if(val <= st[v].mn) return;
	}
	push(v, tl, tr);
	chmax(lv, tl, tm, l, r, val);
	chmax(rv, tm + 1, tr, l, r, val);
	pull(v);
}

void chmin(int v, int tl, int tr, int l, int r, int val) {
	if(tl > tr) return;
	if(tr < l || r < tl || st[v].mx <= val) return;
	if(l <= tl && tr <= r) {
		if(val < st[v].mn) {
			ll d = val - st[v].mn;
			st[v].lazy += d;
			st[v].sum += 1LL * (tr - tl + 1) * d;
			st[v].mn += d;
			st[v].mx += d;
		}
		if(st[v].mx <= val) return;
	}
	push(v, tl, tr);
	chmin(lv, tl, tm, l, r, val);
	chmin(rv, tm + 1, tr, l, r, val);
	pull(v);
}

ll sum(int v, int tl, int tr, int l, int r) {
	if(tr < l || r < tl) return 0;
	if(l <= tl && tr <= r) return st[v].sum;
	push(v, tl, tr);
	return sum(lv, tl, tm, l, r) + sum(rv, tm + 1, tr, l, r);
}

vector<int> distribute_candies(vector<int> C, vector<int> L, vector<int> R, vector<int> V) {
	int N = (int)C.size();
	int Q = (int)L.size();
	for(int i = 0; i < Q; ++i) {
		add(0, 0, N - 1, L[i], R[i], V[i]);
		chmin(0, 0, N - 1, 0, N - 1, C[0]);
		chmax(0, 0, N - 1, 0, N - 1, 0);
	}
	vector<int> ans(N);
	for(int i = 0; i < N; ++i) {
		ans[i] = sum(0, 0, N - 1, i, i);
	}
	return ans;
}

Subtask #1
0 / 3.0

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

Subtask #2
0 / 8.0

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

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 106 ms 7200 KB Output is correct
3 Correct 68 ms 22280 KB Output is correct
4 Correct 308 ms 25776 KB Output is correct
5 Correct 311 ms 30096 KB Output is correct
6 Correct 478 ms 30460 KB Output is correct
7 Correct 398 ms 29808 KB Output is correct

Subtask #4
0 / 29.0

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

Subtask #5
0 / 33.0

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