oj.uz

Submission #438015

# Submission time Handle Problem Language Result Execution time Memory
438015 2021-06-27T12:11:02 Z hhhhaura Distributing Candies (IOI21_candies) C++17
100 / 100
 1202 ms 38212 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 INF 1e9
using namespace std;
#define ll long long int
#define pii pair<ll, ll>
#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);
		}
	}
	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: 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:64:7: warning: unused variable 'l' [-Wunused-variable]
   64 |   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 624 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 1089 ms 38196 KB Output is correct
2 Correct 1103 ms 38212 KB Output is correct
3 Correct 1195 ms 38156 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 766 ms 29572 KB Output is correct
3 Correct 112 ms 7656 KB Output is correct
4 Correct 1136 ms 38164 KB Output is correct
5 Correct 1070 ms 38060 KB Output is correct
6 Correct 1046 ms 38168 KB Output is correct
7 Correct 1108 ms 38204 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 211 ms 27200 KB Output is correct
4 Correct 96 ms 7616 KB Output is correct
5 Correct 329 ms 34176 KB Output is correct
6 Correct 318 ms 34208 KB Output is correct
7 Correct 313 ms 34108 KB Output is correct
8 Correct 326 ms 34088 KB Output is correct
9 Correct 370 ms 34088 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 624 KB Output is correct
5 Correct 4 ms 588 KB Output is correct
6 Correct 1089 ms 38196 KB Output is correct
7 Correct 1103 ms 38212 KB Output is correct
8 Correct 1195 ms 38156 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 766 ms 29572 KB Output is correct
11 Correct 112 ms 7656 KB Output is correct
12 Correct 1136 ms 38164 KB Output is correct
13 Correct 1070 ms 38060 KB Output is correct
14 Correct 1046 ms 38168 KB Output is correct
15 Correct 1108 ms 38204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 211 ms 27200 KB Output is correct
19 Correct 96 ms 7616 KB Output is correct
20 Correct 329 ms 34176 KB Output is correct
21 Correct 318 ms 34208 KB Output is correct
22 Correct 313 ms 34108 KB Output is correct
23 Correct 326 ms 34088 KB Output is correct
24 Correct 370 ms 34088 KB Output is correct
25 Correct 1 ms 204 KB Output is correct
26 Correct 105 ms 7592 KB Output is correct
27 Correct 762 ms 29548 KB Output is correct
28 Correct 1202 ms 38180 KB Output is correct
29 Correct 1133 ms 38068 KB Output is correct
30 Correct 1078 ms 38144 KB Output is correct
31 Correct 1123 ms 38152 KB Output is correct
32 Correct 1086 ms 38160 KB Output is correct