제출 #616087

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
616087		penguinhacker	사탕 분배 (IOI21_candies)	C++17	100 / 100	1106 ms	53088 KiB

candies

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

#define ll long long
#define ar array
#define T ar<ll, 7>

const int mxN=2e5;
const T ID={-1, -1, -1, -1, -1, -1, -1};
// store {sum, min prefix, max prefix, up, down, suffix max, suffix pre}
int n, q;
vector<int> queries[mxN];

T mk(int x) {
	return {x, min(0, x), max(0, x), max(0, x), min(0, x), max(0, x), min(0, x)};
}

T cmb(T a, T 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]}),
		max(a[5]+b[0], b[5]),
		min(a[6]+b[0], b[6]),
	};
}

void pr(T a) {
	for (int i=0; i<7; ++i)
		cout << a[i] << " ";
	cout << endl;
}

struct seg_tree {
	T st[1<<19];

	void upd(int i, T 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, T thing=ID, int u=1, int l=0, int r=q-1) {
		T y=cmb(st[u], thing);
		//cout << "at node [" << l << ", " << r << "]\n"; pr(st[u]), pr(thing), pr(y);
		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;
		//pr(cmb(st[2*u+1], thing));
		return qry1(x, cmb(st[2*u+1], thing), 2*u, l, mid);
	}

	int qry2(int ql, int x, T thing=ID, int u=1, int l=0, int r=q-1) {
		if (r<ql)
			return -1;
		T y=cmb(thing, st[u]);
		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, qry3(ql, mid, 2*u, l, mid)), 2*u+1, mid+1, r);
	}

	T 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 s, bool t) {
		T x=qry3(s, q-1);
		//cout << s << " " << t << endl;
		//pr(x);
		//pr(st[3]);
		return x==ID?0:x[5+t];
	}
} st;

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.st, -1, sizeof(st.st));
	for (int i=0; i<n; ++i) {
		for (int j : queries[i])
			st.upd(j, i==l[j]?mk(v[j]):ID);
		if (st.st[1]==ID||c[i]>=st.st[1][3]) {
			ans[i]=st.gt(0, 0);
			continue;
		}
		//pr(st.st[1]);
		//pr(st.st[2]);
		//pr(st.st[3]);
		int l=st.qry1(c[i]);
		assert(~l);
		//cout << l << endl;
		int r=st.qry2(l, c[i]);
		assert(~r);
		//cout << l << " " << r << endl;
		T x=st.qry3(l, r);
		if (x[3]>=c[i]) {
			assert(x[4]>-c[i]);
			ans[i]=c[i]+st.gt(r+1, 1);
		} else if (x[4]<=-c[i]) {
			assert(x[3]<c[i]);
			ans[i]=st.gt(r+1, 0);
		} else
			assert(0);
	}
	return ans;
}

컴파일 시 표준 에러 (stderr) 메시지

candies.cpp: In member function 'int seg_tree::qry1(int, std::array<long long int, 7>, int, int, int)':
candies.cpp:55:20: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   55 |   if (y==ID||y[3]<x&&y[4]>-x)
candies.cpp: In member function 'int seg_tree::qry2(int, int, std::array<long long int, 7>, int, int, int)':
candies.cpp:71:20: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   71 |   if (y==ID||y[3]<x&&y[4]>-x)

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