oj.uz

답안 #616072

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
616072 2022-07-31T19:53:14 Z penguinhacker 사탕 분배 (IOI21_candies) C++17
0 / 100
 157 ms 98700 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, x, 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);
		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, T thing=ID, int u=1, int l=0, int r=q-1) {
		if (r<ql)
			return -1;
		T 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);
	}

	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;
		}
		int l=st.qry1(c[i]);
		assert(~l);
		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:54:20: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   54 |   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:69:20: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   69 |   if (y==ID||y[3]<x&&y[4]>-x)

Subtask #1
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 33676 KB Output is correct
2 Correct 14 ms 33620 KB Output is correct
3 Runtime error 43 ms 68324 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 157 ms 98700 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 40 ms 68172 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 40 ms 68204 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 33676 KB Output is correct
2 Correct 14 ms 33620 KB Output is correct
3 Runtime error 43 ms 68324 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -