oj.uz

Submission #438014

# Submission time Handle Problem Language Result Execution time Memory
438014 2021-06-27T12:09:49 Z hhhhaura Distributing Candies (IOI21_candies) C++17
100 / 100
 1228 ms 38244 KB 
#define wiwihorz
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma loop-opt(on)

#define rep(i, a, b) for(int i = a; i <= b; i ++)
#define rrep(i, a, b) for(int i = b; i >= a; i--)
#define ceil(a, b) ((a + b - 1) / (b))
#define all(x) x.begin(), x.end()

#define INF 1e9
#define MOD 1000000007
#define eps (1e-9)

using namespace std;

#define ll long long int
#define lld long double
#define pii pair<ll, ll>
#define random mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count())

#ifdef wiwihorz
#define print(a...) cerr << "line " << __LINE__ << ": ", kout("[" + string(#a) + "] = ", a)
void vprint(auto L, auto R) { while(L < R) cerr << *L << " \n"[next(L) == R], ++L;}
void kout() { cerr << endl; }
template<class T1, class ... T2> void kout(T1 a, T2 ... e) { cerr << a << " ", kout(e...);}
#else
#define print(...) 0
#define vprint(...) 0
#endif 

#include "candies.h"
namespace seg {
	int n;
	vector<ll> tag;
	vector<pii> mx, mn;
	int get(int L, int R) { return (L + R) | (L != R);}
	pii get_pii(int nd, int id) {
		if(id == 0) return {mn[nd].first + tag[nd], mn[nd].second};
		else return {mx[nd].first + tag[nd], mx[nd].second};
	}
	void pull(int L, int R) {
		int nd = get(L, R), mid = (L + R) / 2;
		int l = get(L, mid), r = get(mid + 1, R);
		mx[nd] = max(get_pii(l, 1), get_pii(r, 1));
		mn[nd] = min(get_pii(l, 0), get_pii(r, 0));
	}
	void push(int L, int R) {
		int nd = get(L, R), mid = (L + R) / 2;
		int l = get(L, mid), r = get(mid + 1, R);
		tag[l] += tag[nd];
		tag[r] += tag[nd];
		mn[nd].first += tag[nd];
		mx[nd].first += tag[nd];
		tag[nd] = 0;
	}
	void build(int L, int R) {
		int nd = get(L, R), mid = (L + R) / 2;
		if(L == R) mx[nd] = {0, L}, mn[nd] = {0, -L};
		else {
			build(L, mid);
			build(mid + 1, R);
			pull(L, R);
		}
	} 
	void init_(int _n) {
		n = _n;
		tag.assign(2 * n + 1, 0);
		mx.assign(2 * n + 1, {0, 0});
		mn.assign(2 * n + 1, {0, 0});
		build(1, n);
	}
	void modify(int L, int R, int l, int r, int val) {
		int mid = (L + R) / 2, nd = get(L, R);
		if(l > R || r < L) return;
		if(L != R) push(L, R);
		if(l <= L && r >= R) tag[nd] += val;
		else {
			modify(L, mid, l, r, val);
			modify(mid + 1, R, l, r, val);
			pull(L, R);
		}
	}
	int qqq(int L, int R, int x) {
		if(L == R) return tag[get(L, R)] + mx[get(L, R)].first;
		else {
			push(L, R);
			int mid = (L + R) / 2;
			if(x <= mid) return qqq(L, mid, x);
			else return qqq(mid + 1, R, x);
		}
	}
	pii bs(int L, int R, int c, pii big, pii sm) {
		int mid = (L + R) / 2, nd = get(L, R);
		int l = get(L, mid), r = get(mid + 1, R);
		if(L == R) {
			big = max(big, get_pii(nd, 1));
			sm = min(sm, get_pii(nd, 0));
			if(big.second >= -sm.second) return {big.first, 1};
			else return {sm.first, 0};
		}
		else {
			push(L, R);
			ll rmx = max(big, get_pii(r, 1)).first;
			ll rmn = min(sm, get_pii(r, 0)).first;
			if(rmx - rmn >= c) return bs(mid + 1, R, c, big, sm);
			else return bs(L, mid, c, max(big, get_pii(r, 1)), min(sm, get_pii(r, 0)));
		}
	}
	void change(int x, ll val) { modify(1, n, x, n, val);}
	pii query(ll c) { return bs(1, n, c, {-1e18, -1e18}, {1e18, 1e18});}
};
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
    int n = c.size(), m = l.size();
    ll sum = 0;
 	vector<int> ans(n, 0);
 	vector<vector<pii>> ops(n + 1, vector<pii>());
 	seg::init_(m + 3);
 	seg::change(1, -INF);
 	seg::change(2, 2 * INF);
 	seg::change(3, -INF);
 	rep(i, 4, m + 3) {
 		ops[l[i - 4]].push_back({i, v[i - 4]});
 		ops[r[i - 4] + 1].push_back({i, -v[i - 4]});
 	}
 	rep(i, 0, n - 1) {
 		for(auto j : ops[i]) {
 			sum += j.second;
 			seg::change(j.first, j.second);
 		}
 		pii cur = seg::query(c[i]); 
 		ll val = 0;
 		if(cur.second) val = (ll)c[i] + (ll)sum - (ll)cur.first;
 		else val = (ll)sum - (ll)cur.first;
 		ans[i] = val;
 	} 
    return ans;
}

Compilation message

candies.cpp:4: warning: ignoring '#pragma loop ' [-Wunknown-pragmas]
    4 | #pragma loop-opt(on)
      | 
candies.cpp:24:13: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   24 | void vprint(auto L, auto R) { while(L < R) cerr << *L << " \n"[next(L) == R], ++L;}
      |             ^~~~
candies.cpp:24:21: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   24 | void vprint(auto L, auto R) { while(L < R) cerr << *L << " \n"[next(L) == R], ++L;}
      |                     ^~~~
candies.cpp: In function 'std::pair<long long int, long long int> seg::bs(int, int, int, std::pair<long long int, long long int>, std::pair<long long int, long long int>)':
candies.cpp:95:7: warning: unused variable 'l' [-Wunused-variable]
   95 |   int l = get(L, mid), r = get(mid + 1, R);
      |       ^

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 3 ms 588 KB Output is correct
4 Correct 3 ms 588 KB Output is correct
5 Correct 4 ms 588 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1058 ms 38160 KB Output is correct
2 Correct 1112 ms 38164 KB Output is correct
3 Correct 1211 ms 38212 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 774 ms 29564 KB Output is correct
3 Correct 107 ms 7620 KB Output is correct
4 Correct 1088 ms 38168 KB Output is correct
5 Correct 1228 ms 38048 KB Output is correct
6 Correct 1145 ms 38164 KB Output is correct
7 Correct 1042 ms 38100 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 202 ms 27136 KB Output is correct
4 Correct 123 ms 7592 KB Output is correct
5 Correct 329 ms 34176 KB Output is correct
6 Correct 371 ms 34104 KB Output is correct
7 Correct 346 ms 34184 KB Output is correct
8 Correct 351 ms 34104 KB Output is correct
9 Correct 336 ms 34192 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 3 ms 588 KB Output is correct
4 Correct 3 ms 588 KB Output is correct
5 Correct 4 ms 588 KB Output is correct
6 Correct 1058 ms 38160 KB Output is correct
7 Correct 1112 ms 38164 KB Output is correct
8 Correct 1211 ms 38212 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 774 ms 29564 KB Output is correct
11 Correct 107 ms 7620 KB Output is correct
12 Correct 1088 ms 38168 KB Output is correct
13 Correct 1228 ms 38048 KB Output is correct
14 Correct 1145 ms 38164 KB Output is correct
15 Correct 1042 ms 38100 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 202 ms 27136 KB Output is correct
19 Correct 123 ms 7592 KB Output is correct
20 Correct 329 ms 34176 KB Output is correct
21 Correct 371 ms 34104 KB Output is correct
22 Correct 346 ms 34184 KB Output is correct
23 Correct 351 ms 34104 KB Output is correct
24 Correct 336 ms 34192 KB Output is correct
25 Correct 1 ms 204 KB Output is correct
26 Correct 110 ms 7608 KB Output is correct
27 Correct 793 ms 29508 KB Output is correct
28 Correct 1150 ms 38180 KB Output is correct
29 Correct 1173 ms 38152 KB Output is correct
30 Correct 1154 ms 38244 KB Output is correct
31 Correct 1093 ms 38156 KB Output is correct
32 Correct 1174 ms 38152 KB Output is correct