oj.uz

Submission #616087

# Submission time Handle Problem Language Result Execution time Memory
616087 2022-07-31T20:23:26 Z penguinhacker Distributing Candies (IOI21_candies) C++17
100 / 100
 1106 ms 53088 KB 
#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;
}

Compilation message

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.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 33748 KB Output is correct
2 Correct 16 ms 33624 KB Output is correct
3 Correct 16 ms 33764 KB Output is correct
4 Correct 17 ms 33816 KB Output is correct
5 Correct 19 ms 33820 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 935 ms 51256 KB Output is correct
2 Correct 1014 ms 50444 KB Output is correct
3 Correct 960 ms 50284 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 33748 KB Output is correct
2 Correct 410 ms 43724 KB Output is correct
3 Correct 323 ms 39492 KB Output is correct
4 Correct 932 ms 52308 KB Output is correct
5 Correct 1106 ms 52752 KB Output is correct
6 Correct 935 ms 53088 KB Output is correct
7 Correct 527 ms 52300 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 33648 KB Output is correct
2 Correct 15 ms 33680 KB Output is correct
3 Correct 147 ms 39376 KB Output is correct
4 Correct 200 ms 36252 KB Output is correct
5 Correct 454 ms 41708 KB Output is correct
6 Correct 551 ms 41716 KB Output is correct
7 Correct 477 ms 41660 KB Output is correct
8 Correct 445 ms 41700 KB Output is correct
9 Correct 685 ms 41744 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 33748 KB Output is correct
2 Correct 16 ms 33624 KB Output is correct
3 Correct 16 ms 33764 KB Output is correct
4 Correct 17 ms 33816 KB Output is correct
5 Correct 19 ms 33820 KB Output is correct
6 Correct 935 ms 51256 KB Output is correct
7 Correct 1014 ms 50444 KB Output is correct
8 Correct 960 ms 50284 KB Output is correct
9 Correct 14 ms 33748 KB Output is correct
10 Correct 410 ms 43724 KB Output is correct
11 Correct 323 ms 39492 KB Output is correct
12 Correct 932 ms 52308 KB Output is correct
13 Correct 1106 ms 52752 KB Output is correct
14 Correct 935 ms 53088 KB Output is correct
15 Correct 527 ms 52300 KB Output is correct
16 Correct 13 ms 33648 KB Output is correct
17 Correct 15 ms 33680 KB Output is correct
18 Correct 147 ms 39376 KB Output is correct
19 Correct 200 ms 36252 KB Output is correct
20 Correct 454 ms 41708 KB Output is correct
21 Correct 551 ms 41716 KB Output is correct
22 Correct 477 ms 41660 KB Output is correct
23 Correct 445 ms 41700 KB Output is correct
24 Correct 685 ms 41744 KB Output is correct
25 Correct 18 ms 33704 KB Output is correct
26 Correct 170 ms 37388 KB Output is correct
27 Correct 430 ms 43348 KB Output is correct
28 Correct 854 ms 50932 KB Output is correct
29 Correct 874 ms 51456 KB Output is correct
30 Correct 969 ms 51512 KB Output is correct
31 Correct 1095 ms 51724 KB Output is correct
32 Correct 840 ms 51924 KB Output is correct