oj.uz

답안 #1060619

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1060619 2024-08-15T19:17:19 Z AmirAli_H1 사탕 분배 (IOI21_candies) C++17
0 / 100
 96 ms 50512 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 {
	int lazy0;
	pll addx; pll val;
};

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

void addx(int v, ll x) {
	ll d = min(x, t[v].addx.S);
	t[v].addx.S -= d; x -= d; t[v].addx.F += x;
	t[v].val.F += x; t[v].val.F = min(t[v].val.S, t[v].val.F);
}

void subx(int v, ll x) {
	t[v].addx.S += x;
	t[v].val.F -= x; t[v].val.F = max(0ll, t[v].val.F);
}

void setx(int v) {
	t[v].lazy0 = 1; t[v].addx = Mp(0, 0);
	t[v].val.F = 0;
}

node f(node a, node b) {
	node res;
	res.lazy0 = 0; res.addx = Mp(0, 0);
	res.val = b.val;
	return res;
}

void shift(int v, int tl, int tr) {
	int set0 = t[v].lazy0; t[v].lazy0 = 0;
	pll x = t[v].addx; t[v].addx = Mp(0, 0);
	if (tr - tl == 1) return ;
	for (int u : {2 * v + 1, 2 * v + 2}) {
		if (set0) setx(u);
		addx(u, x.F); subx(u, x.S);
	}
}

void build(int v, int tl, int tr) {
	t[v].lazy0 = 0; t[v].addx = Mp(0, 0);
	if (tr - tl == 1) {
		t[v].val = Mp(0, A[tl].F);
		return ;
	}
	int mid = (tl + tr) / 2;
	build(2 * v + 1, tl, mid); build(2 * v + 2, mid, tr);
	t[v] = f(t[2 * v + 1], t[2 * v + 2]);
}

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) {
		addx(v, 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);
	t[v] = f(t[2 * v + 1], t[2 * v + 2]);
}

void sub_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) {
		subx(v, x);
		return ;
	}
	int mid = (tl + tr) / 2;
	sub_val(2 * v + 1, tl, mid, l, r, x); sub_val(2 * v + 2, mid, tr, l, r, x);
	t[v] = f(t[2 * v + 1], t[2 * v + 2]);
}

void set_zero(int v, int tl, int tr, int l, int r) {
	l = max(l, tl); r = min(r, tr);
	if (l >= tr || r <= tl) return ;
	shift(v, tl, tr);
	if (l == tl && r == tr) {
		setx(v);
		return ;
	}
	int mid = (tl + tr) / 2;
	set_zero(2 * v + 1, tl, mid, l, r); set_zero(2 * v + 2, mid, tr, l, r);
	t[v] = f(t[2 * v + 1], t[2 * v + 2]);
}

int get_ind(int v, int tl, int tr, int x) {
	shift(v, tl, tr);
	if (tr - tl == 1) {
		if (t[v].val.F >= x) return tl;
		else return tr;
	}
	int mid = (tl + tr) / 2;
	if (t[2 * v + 1].val.F >= x) return get_ind(2 * v + 1, tl, mid, x);
	else return get_ind(2 * v + 2, mid, tr, x);
}

void get_ans(int v, int tl, int tr) {
	shift(v, tl, tr);
	if (tr - tl == 1) {
		ans[A[tl].S] = t[v].val.F;
		return ;
	}
	int mid = (tl + tr) / 2;
	get_ans(2 * v + 1, tl, mid); get_ans(2 * v + 2, mid, tr);
}

vector<int> distribute_candies(vector<int> c, vector<int> lx, vector<int> rx, vector<int> vx) {
	n = len(c); q = len(lx);
	for (int i = 0; i < n; i++) A[i] = Mp(c[i], i);
	for (int i = 0; i < q; i++) Q[i] = Mp(Mp(lx[i], rx[i] + 1), vx[i]);
	sort(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;
		if (x >= 0) add_val(0, 0, n, 0, n, x);
		else {
			x = -x;
			int j = get_ind(0, 0, n, x);
			set_zero(0, 0, n, 0, j); sub_val(0, 0, n, j, n, x);
		}
	}
	
	ans.clear(); ans.resize(n);
	get_ans(0, 0, n);
	return ans;
}

Compilation message

candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:145:7: warning: unused variable 'l' [-Wunused-variable]
  145 |   int l = Q[i].F.F, r = Q[i].F.S, x = Q[i].S;
      |       ^
candies.cpp:145:21: warning: unused variable 'r' [-Wunused-variable]
  145 |   int l = Q[i].F.F, r = Q[i].F.S, x = Q[i].S;
      |                     ^

Subtask #1
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 35416 KB Output is correct
2 Incorrect 4 ms 35420 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 96 ms 50512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 35416 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 35420 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 35416 KB Output is correct
2 Incorrect 4 ms 35420 KB Output isn't correct
3 Halted 0 ms 0 KB -