Submission #616038

#	Time	Username	Problem	Language	Result	Execution time	Memory
616038		penguinhacker	사탕 분배 (IOI21_candies)	C++17	0 / 100	160 ms	82004 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

const int mxN=2e5;
const ar<ll, 5> ID={-1, -1, -1, -1, -1};
// store {sum, min, max, up, down}
int n, q;
vector<int> queries[mxN];
ar<ll, 5> st[1<<19];

ar<ll, 5> mk(int x) {
	return {x, x, x, max(0, x), min(0, x)};
}

ar<ll, 5> cmb(ar<ll, 5> a, ar<ll, 5> b) {
	if (a==ID||b==ID)
		return a!=ID?a:b;
	return {
		a[0]+b[0],
		min(a[1], a[0]+b[1]),
		max(a[2], a[0]+b[2]),
		max({a[3], b[3], a[0]+b[2]-a[1]}),
		min({a[4], b[4], a[0]+b[1]-a[2]})
	};
}

void upd(int i, ar<ll, 5> x, int u=1, int l=0, int r=q-1) {
	if (l==r) {
		st[u]=x;
		return;
	}
	int mid=(l+r)/2;
	i<=mid?upd(i, x, 2*u, l, mid):upd(i, x, 2*u+1, mid+1, r);
	st[u]=cmb(st[2*u], st[2*u+1]);
}

int qry1(int x, ar<ll, 5> thing=ID, int u=1, int l=0, int r=q-1) {
	ar<ll, 5> y=cmb(st[u], thing);
	if (y==ID||y[3]<x&&y[4]>-x)
		return -1;
	if (l==r)
		return l;
	int mid=(l+r)/2;
	int rs=qry1(x, thing, 2*u+1, mid+1, r);
	if (rs!=-1)
		return rs;
	return qry1(x, cmb(st[2*u+1], thing), 2*u, l, mid);
}

int qry2(int ql, int x, ar<ll, 5> thing=ID, int u=1, int l=0, int r=q-1) {
	if (r<ql)
		return -1;
	ar<ll, 5> y=cmb(st[u], thing);
	if (y==ID||y[3]<x&&y[4]>-x)
		return -1;
	if (l==r)
		return l;
	int mid=(l+r)/2;
	int ls=qry2(ql, x, thing, 2*u, l, mid);
	if (ls!=-1)
		return ls;
	return qry2(ql, x, cmb(thing, st[2*u]), 2*u+1, mid+1, r);
}

ar<ll, 5> qry3(int ql, int qr, int u=1, int l=0, int r=q-1) {
	if (l>qr||r<ql)
		return ID;
	if (ql<=l&&r<=qr)
		return st[u];
	int mid=(l+r)/2;
	return cmb(qry3(ql, qr, 2*u, l, mid), qry3(ql, qr, 2*u+1, mid+1, r));
}

ll gt(int ql, int qr) {
	ar<ll, 5> x=qry3(ql, qr);
	return x==ID?0:x[0];
}

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
	n=c.size(), q=l.size();
	vector<int> ans(n);
	for (int i=0; i<q; ++i) {
		queries[l[i]].push_back(i);
		if (r[i]+1<n)
			queries[r[i]+1].push_back(i);
	}
	memset(st, -1, sizeof(st));
	for (int i=0; i<n; ++i) {
		for (int j : queries[i])
			upd(j, i==l[j]?mk(v[j]):ID);
		if (st[1]==ID||c[i]>=st[1][3]) {
			ans[i]=max(0ll, gt(0, q-1));
			continue;
		}
		int l=qry1(c[i]);
		assert(~l);
		int r=qry2(l, c[i]);
		assert(~r);
		ar<ll, 5> x=qry3(l, r);
		if (x[3]>=c[i]) {
			assert(x[4]>-c[i]);
			ans[i]=min((ll)c[i], c[i]+gt(r+1, q-1));
		} else if (x[4]<=-c[i]) {
			assert(x[3]<c[i]);
			ans[i]=max(0ll, gt(r+1, q-1));
		} else
			assert(0);
	}
	return ans;
}

Compilation message (stderr)

candies.cpp: In function 'int qry1(int, std::array<long long int, 5>, int, int, int)':
candies.cpp:43:19: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   43 |  if (y==ID||y[3]<x&&y[4]>-x)
candies.cpp: In function 'int qry2(int, int, std::array<long long int, 5>, int, int, int)':
candies.cpp:58:19: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   58 |  if (y==ID||y[3]<x&&y[4]>-x)

• Subtask 1: 0 / 3
• Subtask 2: 0 / 8
• Subtask 3: 0 / 27
• Subtask 4: 0 / 29
• Subtask 5: 0 / 33