oj.uz

답안 #436654

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
436654 2021-06-24T17:39:49 Z shrimb 사탕 분배 (IOI21_candies) C++17
11 / 100
 509 ms 8900 KB 
#include"bits/stdc++.h"
// #define int long long
#define endl '\n'
using namespace std;
long long N, Left, Right, Value;
long long seg[2000001], lazy1[2000001], lazy2[2000001], pref[200001]; // lazy2[i] = 1 ? max : 0

#define sum(l,r) (r>0 ? pref[r-1] : 0) - (l>1 ? pref[l-2] : 0)

void Spread2 (int l, int r, int ind) {
	if (l != r) {
		lazy1[ind * 2] += lazy1[ind];
		lazy1[ind * 2 + 1] += lazy1[ind];
		int mid = (l + r) / 2;
		seg[ind * 2] += (mid - l + 1) * lazy1[ind];
		seg[ind * 2 + 1] += (r - mid) * lazy1[ind];
	}
	lazy1[ind] = 0;
}

void Spread1 (int l, int r, int ind) {
	if (lazy2[ind] == 1 and l != r) {
		lazy2[ind * 2] = 1;
		lazy2[ind * 2 + 1] = 1;
		lazy1[ind * 2] = 0;
		lazy1[ind * 2 + 1] = 0;
		int mid = (l + r) / 2;
		seg[ind * 2] = sum(l, mid);
		seg[ind * 2 + 1] = sum(mid + 1, r);
	}
	else if (lazy2[ind] == -1 and l != r) {
		lazy2[ind * 2] = -1;
		lazy2[ind * 2 + 1] = -1;
		lazy1[ind * 2] = 0;
		lazy1[ind * 2 + 1] = 0;
		seg[ind * 2] = 0;
		seg[ind * 2 + 1] = 0;
	}
	lazy2[ind] = 0;
}

int Query (int l = 1, int r = N, int ind = 1) {
	if (l > Right || r < Left) return 0;
	Spread1(l, r, ind);
	Spread2(l, r, ind);
	if (l >= Left and r <= Right) return seg[ind];
	int mid = (l + r) / 2;
	return Query(l, mid, ind * 2) + Query(mid + 1, r, ind * 2 + 1);
}

void Update (int l = 1, int r = N, int ind = 1) {
	if (l > Right || r < Left) return;
	Spread1(l, r, ind);
	Spread2(l, r, ind);
	if (l >= Left and r <= Right) {
		if (Value == 2000000000000000000) { // max
			lazy2[ind] = 1;
			seg[ind] = sum(l, r);
		} else if (Value == 2000000000000000000 - 1) { // 0
			lazy2[ind] = -1;
			seg[ind] = 0;
		} else { // add
			lazy1[ind] += Value;
			seg[ind] += (r - l + 1) * Value;
		}
		return;
	}
	int mid = (l + r) / 2;
	Update(l, mid, ind * 2);
	Update(mid + 1, r, ind * 2 + 1);
	seg[ind] = seg[ind * 2] + seg[ind * 2 + 1];
}

vector<int> distribute_candies (vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
	int n = c.size();
	int q = l.size();
	N = exp2(ceil(log2(n)));

	bool st1 = (n <= 2000 and q <= 2000);
	bool st2 = 1; for (int i = 0 ; i < q ; i++) if (v[i] < 0) st2 = 0;
	bool st3 = 1; for (int i = 0 ; i < q ; i++) if (l[i] != 0 || r[i] != n - 1) st3 = 0;
	// st1 = st2 = 0;
	if (st1) {
		vector<int> ret(n, 0);
		for (int i = 0 ; i < q ; i++) {
			for (int j = l[i] ; j <= r[i] ; j++) {
				ret[j] = max(0, min(c[j], ret[j] + v[i]));
			}
		}
		return ret;
	}
	if (st2) {
		vector<int> ret(n, 0);
		// vector<long long> pref(n + 1, 0);
		for (int i = 0 ; i < q ; i++) {
			pref[l[i]] += v[i];
			pref[r[i] + 1] -= v[i];
		}
		for (int i = 1 ; i < n ; i++) pref[i] += pref[i-1];
		for (int i = 0 ; i < n ; i++) ret[i] = min((long long)c[i], pref[i]);
		return ret;
	}
	if (st3) {
		vector<int> ans(n);
		vector<pair<int,int>> srt;
		for (int i = 0 ; i < n ; i++) srt.emplace_back(c[i], i);
		sort(srt.begin(), srt.end());
		for (int i = 0 ; i < n ; i++) {
			pref[i] = srt[i].first + (i ? pref[i-1] : 0);
		}
		for (int i = 0 ; i < q ; i++) {
			int l = 0, r = n;
			Left = Right = 1;
			bool _F = (v[i] < 0 ? Query() + v[i] <= 0 : Query() + v[i] >= c[0]);
			while (r - l > 1) {
				int mid = (l + r) / 2;
				Left = Right = mid + 1;
				int val = Query();
				// cerr << mid + 1 << " " << val << " " << c[srt[mid].second] << " " << v[i] << endl;
				if (v[i] < 0) {
					if (val + v[i] <= 0) {l = mid;}
					else r = mid;
				} else {
					if (val + v[i] >= c[srt[mid].second]) {l = mid;}
					else r = mid;
				}
			}
			if (_F) {
				Left = 1, Right = l+1;
				// cerr << "1: " << Left << " " << Right << endl;
				Value = 2000000000000000000;
				if (v[i] < 0) Value--;
				// cerr << Value << " " << v[i] << endl;
				Update();
			}
			if (!_F or (_F and l < (n - 1))) {
				if (!_F) Left = 1;
				else Left = l+2;
				Right = n;
				// cerr << "2: " << Left << " " << Right << endl;
				Value = v[i];
				Update();
			}
		}
		vector<int> ret(n);
		for (int i = 0 ; i < n ; i++) {
			Left = Right = i + 1;
			ret[srt[i].second] = Query();
		}
		return ret;
	}
}

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:152:1: warning: control reaches end of non-void function [-Wreturn-type]
  152 | }
      | ^

Subtask #1
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 3 ms 332 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 130 ms 8896 KB Output is correct
2 Correct 117 ms 8900 KB Output is correct
3 Correct 117 ms 8812 KB Output is correct

Subtask #3
0 / 27.0

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

Subtask #4
0 / 29.0

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

Subtask #5
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 3 ms 332 KB Output is correct
6 Correct 130 ms 8896 KB Output is correct
7 Correct 117 ms 8900 KB Output is correct
8 Correct 117 ms 8812 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Incorrect 474 ms 5212 KB Output isn't correct
11 Halted 0 ms 0 KB -