oj.uz

답안 #791273

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
791273 2023-07-23T21:15:14 Z IvanJ 사탕 분배 (IOI21_candies) C++17
100 / 100
 1865 ms 35884 KB 
#include "candies.h"
#include<bits/stdc++.h>

#define pb push_back
#define x first
#define y second
#define all(a) (a).begin(), (a).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;

const int maxn = 2e5 + 5, inf = 1e9;
const ll INF = 1e18;

struct Data {
	ll lo, hi;
	int min_idx;
};

Data merge(Data A, Data B) {
	Data ret = {INF, -INF, -1};
	ret.lo = min(A.lo, B.lo);
	ret.hi = max(A.hi, B.hi);
	ret.min_idx = A.min_idx;
	if(ret.lo == B.lo)
		ret.min_idx = B.min_idx;
	return ret;
}

struct Seg {
	int pot = 1, n;
	vector<Data> T;
	vector<ll> L;
	void init(int _n) {
		n = _n;
		while(pot < n) pot <<= 1;
		for(int i = 0;i < (pot << 1);i++) T.pb({0, 0, -1}), L.pb(0);
		for(int i = 0;i < n;i++) T[i + pot].min_idx = i;
		for(int i = pot - 1;i > 0;i--) 
			T[i] = merge(T[i * 2], T[i * 2 + 1]);
	}
	
	void prop(int x) {
		if(L[x] == 0) return;
		T[x].lo += L[x];
		T[x].hi += L[x];
		if(x < pot) 
			L[x * 2] += L[x], L[x * 2 + 1] += L[x];
		L[x] = 0;
	}
	
	void add(int x, int lo, int hi, int a, int b, ll v) {
		prop(x);
		if(hi < a || b < lo) return;
		if(a <= lo && hi <= b) {
			L[x] += v;
			prop(x);
			return;
		} 
		int mid = (lo + hi) / 2;
		add(x * 2, lo, mid, a, b, v);
		add(x * 2 + 1, mid + 1, hi, a, b, v);
		T[x] = merge(T[x * 2], T[x * 2 + 1]);
	}
	
	void update(int x, ll v) {add(1, 0, pot - 1, x, n - 1, v);}
	
	Data get_min(int x, int lo, int hi, int a, int b) {
		prop(x);
		if(hi < a || b < lo) return {INF, -INF, -1};
		if(a <= lo && hi <= b) return T[x];
		int mid = (lo + hi) / 2;
		Data l = get_min(x * 2, lo, mid, a, b);
		Data r = get_min(x * 2 + 1, mid + 1, hi, a, b);
		if(l.min_idx == -1) return r;
		if(r.min_idx == -1) return l;
		if(l.lo < r.lo) return l;
		return r;
	}
	
	int query(int lo, int hi) {return get_min(1, 0, pot - 1, lo, hi).min_idx;}
	
	Data get_range(int x, int lo, int hi, int a, int b) {
		prop(x);
		if(hi < a || b < lo) return {INF, -INF, -1};
		if(a <= lo && hi <= b) return T[x];
		int mid = (lo + hi) / 2;
		Data l = get_range(x * 2, lo, mid, a, b);
		Data r = get_range(x * 2 + 1, mid + 1, hi, a, b);
		return merge(l, r);
	}
	
	Data query2(int lo, int hi) {return get_range(1, 0, pot - 1, lo, hi);}
	
	int solve(ll c) {
		int lo = 0, hi = n - 1, ans = -1;
		while(lo <= hi) {
			int mid = (lo + hi) / 2;
			Data D = query2(mid, n - 1);
			if(D.hi - D.lo < c) ans = mid, hi = mid - 1;
			else lo = mid + 1;
		}
		return ans;
	}
	
	ll get_val(int x, int lo, int hi, int X) {
		prop(x);
		if(lo == hi) return T[x].lo;
		int mid = (lo + hi) / 2;
		if(X <= mid) return get_val(x * 2, lo, mid, X);
		return get_val(x * 2 + 1, mid + 1, hi, X);
	}
	
	ll get(int x) {return get_val(1, 0, pot - 1, x);}
};

int n, q;
vector<ii> sweep[maxn];
Seg S;

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
    n = (int)c.size();
    q = (int)l.size();
    S.init(q + 2);
    vector<int> ans(n, 0);
    
    for(int i = 0;i < q;i++) 
		sweep[l[i]].pb({v[i], i + 2}), sweep[r[i] + 1].pb({-v[i], i + 2});
	
	S.update(0, inf);
	S.update(1, -inf);
	for(int i = 0;i < n;i++) {
		for(ii p : sweep[i]) 
			S.update(p.y, p.x);
	
		int t_max = S.solve(c[i]);
		ll h1 = S.get(t_max - 1), h2 = S.get(t_max);
		Data D = S.query2(t_max, q + 1);
		ll X = 0;
		X = c[i] - (D.hi - D.lo);
		if(h1 > h2) X = 0;
		int mini = S.query(t_max, q + 1);
		ans[i] = S.get(q + 1) - S.get(mini) + X;
	}
    return ans;
}

Subtask #1
3.0 / 3.0

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

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1682 ms 35788 KB Output is correct
2 Correct 1831 ms 35760 KB Output is correct
3 Correct 1858 ms 35836 KB Output is correct

Subtask #3
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5008 KB Output is correct
2 Correct 297 ms 30880 KB Output is correct
3 Correct 584 ms 9080 KB Output is correct
4 Correct 1806 ms 35832 KB Output is correct
5 Correct 1865 ms 35760 KB Output is correct
6 Correct 1591 ms 35808 KB Output is correct
7 Correct 1607 ms 35884 KB Output is correct

Subtask #4
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 5000 KB Output is correct
3 Correct 148 ms 32080 KB Output is correct
4 Correct 455 ms 7956 KB Output is correct
5 Correct 1385 ms 34624 KB Output is correct
6 Correct 1314 ms 34652 KB Output is correct
7 Correct 1196 ms 34656 KB Output is correct
8 Correct 1446 ms 34648 KB Output is correct
9 Correct 1575 ms 34652 KB Output is correct

Subtask #5
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 5000 KB Output is correct
3 Correct 4 ms 5204 KB Output is correct
4 Correct 5 ms 5204 KB Output is correct
5 Correct 11 ms 5264 KB Output is correct
6 Correct 1682 ms 35788 KB Output is correct
7 Correct 1831 ms 35760 KB Output is correct
8 Correct 1858 ms 35836 KB Output is correct
9 Correct 3 ms 5008 KB Output is correct
10 Correct 297 ms 30880 KB Output is correct
11 Correct 584 ms 9080 KB Output is correct
12 Correct 1806 ms 35832 KB Output is correct
13 Correct 1865 ms 35760 KB Output is correct
14 Correct 1591 ms 35808 KB Output is correct
15 Correct 1607 ms 35884 KB Output is correct
16 Correct 3 ms 4948 KB Output is correct
17 Correct 3 ms 5000 KB Output is correct
18 Correct 148 ms 32080 KB Output is correct
19 Correct 455 ms 7956 KB Output is correct
20 Correct 1385 ms 34624 KB Output is correct
21 Correct 1314 ms 34652 KB Output is correct
22 Correct 1196 ms 34656 KB Output is correct
23 Correct 1446 ms 34648 KB Output is correct
24 Correct 1575 ms 34652 KB Output is correct
25 Correct 3 ms 4948 KB Output is correct
26 Correct 503 ms 7900 KB Output is correct
27 Correct 321 ms 30856 KB Output is correct
28 Correct 1814 ms 35768 KB Output is correct
29 Correct 1674 ms 35764 KB Output is correct
30 Correct 1751 ms 35788 KB Output is correct
31 Correct 1613 ms 35640 KB Output is correct
32 Correct 1574 ms 35756 KB Output is correct