Submission #438015

#	Time	Username	Problem	Language	Result	Execution time	Memory
438015		hhhhaura	Distributing Candies (IOI21_candies)	C++17	100 / 100	1202 ms	38212 KiB

candies

#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 (stderr)

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 / 3
• Subtask 2: 8 / 8
• Subtask 3: 27 / 27
• Subtask 4: 29 / 29
• Subtask 5: 33 / 33