oj.uz

답안 #483883

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
483883 2021-11-01T08:05:34 Z 8e7 사탕 분배 (IOI21_candies) C++17
29 / 100
 474 ms 38932 KB 
//Challenge: Accepted
#include "candies.h"
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
using namespace std;
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ...b) {
	cout << a << " ", debug(b ...);
};
template<class T> void pary (T l, T r) {
	while (l!= r) cout << *l << " ", l++;
	cout << endl;
};
#define ll long long
#define maxn 200005
#define pii pair<ll, ll>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
const ll inf = 1LL<<60;
struct segtree{
	ll ma[4 * maxn], mi[4 * maxn], tag[4 * maxn];	
	int ama[4 * maxn], ami[4 * maxn];
	void init(int cur, int l, int r) {
		if (r <= l) return;
		if (r - l == 1) {
			ama[cur] = ami[cur] = l;
			return;
		}
		int mid = (l + r) / 2;
		init(cur * 2, l, mid), init(cur * 2 + 1, mid, r);
		ama[cur] = ami[cur] = l;
	}
	void push(int cur, int l, int r) {
		if (!tag[cur]) return;
		ma[cur] += tag[cur], mi[cur] += tag[cur];
		if (r - l > 1) tag[cur * 2] += tag[cur], tag[cur * 2 + 1] += tag[cur];
		tag[cur] = 0;		
	}
	void pull(int cur, int l, int r) {
		push(cur, l, r);
		if (r - l < 2) return;
		int m = (l + r) / 2;
		push(cur * 2, l, m), push(cur * 2 + 1, m, r);	
		if (ma[cur*2] > ma[cur*2+1]) ma[cur] = ma[cur*2], ama[cur] = ama[cur*2];
		else ma[cur] = ma[cur*2+1], ama[cur] = ama[cur*2+1];
		if (mi[cur*2] < mi[cur*2+1]) mi[cur] = mi[cur*2], ami[cur] = ami[cur*2];
		else mi[cur] = mi[cur*2+1], ami[cur] = ami[cur*2+1];
	}
	void modify(int cur, int l, int r, int ql, int qr, ll val) {
		if (r <= l || ql >= r || qr <= l) return;
		push(cur, l, r);
		if (ql <= l && qr >= r) {
			tag[cur] += val;return;
		}
		int mid = (l + r) / 2;
		modify(cur * 2, l, mid, ql, qr, val), modify(cur*2+1, mid, r, ql, qr, val);
		pull(cur, l, r);
		//debug("seg", l, r, ma[cur], mi[cur]);
	}
	pii search(int cur, int l, int r,ll big, ll small,ll c) { //maximum id 
		push(cur, l, r);
		if (max(big, ma[cur]) - min(small, mi[cur]) <= c) return make_pair(-1, 0);
		if (r - l == 1) {
			return {l, (ma[cur] - small > c ? 0 : c)};
		}
		int m = (l + r) / 2;
		if (max(ma[cur*2+1], big) - min(small, mi[cur*2+1]) > c) {
			return search(cur*2+1, m, r, big, small, c);
		} else {
			return search(cur*2, l, m, max(ma[cur*2+1], big), min(small, mi[cur*2+1]), c);
		}
	}
	pii getval(int cur, int l, int r, int ql, int qr) { //returns max, min of segment
		if (r <= l || ql >= r || qr <= l) return {-inf, inf};
		push(cur, l, r);
		if (ql <= l && qr >= r) {
			pull(cur, l, r);
			return {ma[cur], mi[cur]};
		}
		int m = (l + r) / 2;
		pii lef = getval(cur * 2, l, m, ql, qr), rig = getval(cur*2+1, m, r, ql, qr);
		return make_pair(max(lef.ff, rig.ff), min(lef.ss, rig.ss));
	}
}seg;
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
	vector<pii> ch[maxn];
    int n = c.size(), q = v.size();
	vector<int> ret(n, 0);
	for (int i = 0;i < q;i++) {
		ch[l[i]].push_back({v[i], i+1});
		ch[r[i] + 1].push_back({-v[i], i+1});
	}
	q++;
	seg.init(1, 0, q);	
	for (int i = 0;i < n;i++) {
		for (auto p:ch[i]) {
			//debug("mod", p.ss, q, p.ff);
			seg.modify(1, 0, q, p.ss, q, p.ff);	
		}
		pii p = seg.search(1, 0, q, -inf, inf, c[i]), last = seg.getval(1, 0, q, q-1, q);
		//debug(p.ff, p.ss);
		if (p.ff == -1) {
			pii all = seg.getval(1, 0, q, 0, q);
			ret[i] = last.ff - all.ss;
			//debug(0, last.ff, all.ss);
		} else {
			pii rem = seg.getval(1, 0, q, p.ff + 1, q);
			if (p.ss == 0) ret[i] = last.ff - rem.ss;
			else ret[i] = c[i] - (rem.ff - last.ff);
			//debug(1, last.ff, rem.ff, rem.ss, p.ss);
		}
	}
	return ret;
}
/*
3
10 15 13
6
0 2 20
0 1 -11
1 2 5
0 1 7
0 2 -14
0 2 11
*/

Subtask #1
0 / 3.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 27.0

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

Subtask #4
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 108 ms 32448 KB Output is correct
4 Correct 81 ms 7752 KB Output is correct
5 Correct 208 ms 34948 KB Output is correct
6 Correct 215 ms 35008 KB Output is correct
7 Correct 217 ms 34992 KB Output is correct
8 Correct 227 ms 34984 KB Output is correct
9 Correct 216 ms 34992 KB Output is correct

Subtask #5
0 / 33.0

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