oj.uz

답안 #536016

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
536016 2022-03-12T06:43:36 Z grt 사탕 분배 (IOI21_candies) C++17
32 / 100
 374 ms 32392 KB 
#include <bits/stdc++.h>
#define PB push_back
#define ST first
#define ND second

//#pragma GCC optimize ("O3")
//#pragma GCC target("tune=native")

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

using namespace std;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;

const int nax = 200 * 1000 + 10;
const ll INF = 1e18;
int n, q;
vector<pi>evs[nax];

struct Node {
	ll g, mi, mx;
};

Node T[(1 << 19)];

void puttag(int v, int x) {
	T[v].mi += x;
	T[v].mx += x;
	T[v].g += x;
}

void push(int v) {
	puttag(v << 1, T[v].g);
	puttag(v << 1 | 1, T[v].g);
	T[v].g = 0;
}

void merge(int v) {
	T[v].mi = min(T[v << 1].mi, T[v << 1 | 1].mi) + T[v].g;
	T[v].mx = max(T[v << 1].mx, T[v << 1 | 1].mx) + T[v].g;
}

void upd(int a, int b, int x, int l = 0, int r = q, int v = 1) {
	if(a <= l && r <= b) {
		puttag(v, x);
		return;
	}
	push(v);
	int mid = (l + r) >> 1;
	if(a <= mid) upd(a, b, x, l, mid, v << 1);
	if(mid < b) upd(a, b, x, mid + 1, r, v << 1 | 1);
	merge(v);
}

tuple<int,ll,ll,ll> ask(int k) {
	int v = 1, l = 0, r = q;
	ll mi = INF, mx = -INF;
	while(l != r) {
		int mid = (l + r) >> 1;
		push(v);
		if(max(mx, T[v << 1 | 1].mx) - min(mi, T[v << 1 | 1].mi) > k) {
			v = v << 1 | 1;
			l = mid + 1;
		} else {
			mx = max(mx, T[v << 1 | 1].mx);
			mi = min(mi, T[v << 1 | 1].mi);
			v = v << 1;
			r = mid;
		}
	}
	mi = min(mi, T[v].mi);
	mx = max(mx, T[v].mx);
	return {l, mi, mx, T[v].mi};
}

vi distribute_candies(vi _c, vi _l, vi _r, vi _v) {
	n = (int)_c.size();
	q = (int)_l.size();
	for(int i = 0; i < q; ++i) {
		evs[_l[i]].emplace_back(i + 1, _v[i]);
		evs[_r[i] + 1].emplace_back(i + 1, -_v[i]);
	}
	vi ans(n);
	ll sum = 0;
	for(int i = 0; i < n; ++i) {
		for(auto &[a,b] : evs[i]) {
			upd(a, q, b);
			sum += b;
		}
		auto [p, a, b, val] = ask(_c[i]);
		if(max(b,val) - min(val,a) <= _c[i]) {
			ans[i] = sum - min(val, a);
		} else {
			if(val == a) {
				//cerr << _c[i] + sum - b << "\n";
				ans[i] = _c[i] + sum - b;
			} else {
				//cerr << sum - a << "\n";
				ans[i] = sum - a;
			}
		}
	}
	return ans;
}

//int main() {
	//ios_base::sync_with_stdio(0);
	//cin.tie(0);
	//distribute_candies({10, 15, 13}, {0, 0}, {2, 1}, {20, -11});
//}

Subtask #1
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4956 KB Output is correct
3 Correct 4 ms 5204 KB Output is correct
4 Correct 4 ms 5128 KB Output is correct
5 Correct 5 ms 5204 KB Output is correct

Subtask #2
0 / 8.0

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

Subtask #3
0 / 27.0

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

Subtask #4
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4992 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 113 ms 26080 KB Output is correct
4 Correct 66 ms 8388 KB Output is correct
5 Correct 182 ms 28324 KB Output is correct
6 Correct 206 ms 31748 KB Output is correct
7 Correct 193 ms 32280 KB Output is correct
8 Correct 210 ms 30840 KB Output is correct
9 Correct 169 ms 32392 KB Output is correct

Subtask #5
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4956 KB Output is correct
3 Correct 4 ms 5204 KB Output is correct
4 Correct 4 ms 5128 KB Output is correct
5 Correct 5 ms 5204 KB Output is correct
6 Incorrect 374 ms 31392 KB Output isn't correct
7 Halted 0 ms 0 KB -