Submission #462314

#	Time	Username	Problem	Language	Result	Execution time	Memory
462314		AdamGS	사탕 분배 (IOI21_candies)	C++17	0 / 100	192 ms	37912 KiB

candies

#include "candies.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=2e5+7;
const ll INF=1e18+7;
ll F1[4*LIM], F2[4*LIM], mi[4*LIM], ma[4*LIM], sufix[LIM], N=1;
void upd(int v, ll x) {
	v+=N;
	mi[v]=ma[v]=x;
	v/=2;
	while(v) {
		mi[v]=min(mi[2*v], mi[2*v+1]);
		ma[v]=max(ma[2*v], ma[2*v+1]);
		v/=2;
	}
}
ll cntmi(int l, int r) {
	l+=N; r+=N;
	ll ans=min(mi[l], mi[r]);
	while(l/2!=r/2) {
		if(l%2==0) ans=min(ans, mi[l+1]);
		if(r%2==1) ans=min(ans, mi[r-1]);
		l/=2; r/=2;
	}
	return ans;
}
ll cntma(int l, int r) {
	l+=N; r+=N;
	ll ans=max(ma[l], ma[r]);
	while(l/2!=r/2) {
		if(l%2==0) ans=max(ans, ma[l+1]);
		if(r%2==1) ans=max(ans, ma[r-1]);
		l/=2; r/=2;
	}
	return ans;
}
int znajdz_gore(int v, int l, int r, ll x) {
	if(l==r) return l;
	if(F1[v]<x) return -1;
	int mid=(l+r)/2;
	if(F1[2*v+1]>=x) return znajdz_gore(2*v+1, mid+1, r, x);
	else return znajdz_gore(2*v, l, mid, x);
}
int znajdz_dol(int v, int l, int r, ll x) {
	if(l==r) return l;
	if(F2[v]<x) return -1;
	int mid=(l+r)/2;
	if(F2[2*v+1]>=x) return znajdz_dol(2*v+1, mid+1, r, x);
	else return znajdz_dol(2*v, l, mid, x);
}
vector<int>solve(vector<ll>c, vector<ll>v) {
	ll n=c.size(), q=v.size();
	for(int i=q-1; i>=0; --i) sufix[i]=sufix[i+1]+v[i];
	while(N<=q) N*=2;
	stack<pair<ll,ll>>kolma, kolmi;
	kolma.push({INF, -1});
	kolmi.push({-INF, -1});
	ll sum=0;
	rep(i, q) {
		sum+=v[i];
		upd(i+1, sum);
		while(kolma.top().st<sum) kolma.pop();
		F1[N+i]=sum-cntmi(kolma.top().nd+1, i+1);
		while(kolmi.top().st>sum) kolmi.pop();
		F2[N+i]=cntma(kolmi.top().nd+1, i+1)-sum;
		kolma.push({sum, i});
		kolmi.push({sum, i});
	}
	for(int i=N-1; i>=0; --i) {
		F1[i]=max(F1[2*i], F1[2*i+1]);
		F2[i]=max(F2[2*i], F2[2*i+1]);
	}
	vector<int>ans;
	rep(i, n) {
		int gora=znajdz_gore(1, 0, N-1, c[i]);
		int dol=znajdz_dol(1, 0, N-1, c[i]);
		if(gora>=dol) {
			if(gora==-1) {
				ans.pb(sufix[0]);
			} else {
				ans.pb(c[i]+sufix[gora+1]);
			}
		} else {
			ans.pb(sufix[dol+1]);
		}
	}
	return ans;
}
vector<int>distribute_candies(vector<int>c, vector<int>l, vector<int>r, vector<int>v) {
	vector<ll>c1, v1;
	for(auto i : c) c1.pb(i);
	for(auto i : v) v1.pb(i);
	return solve(c1, v1);
}
/*int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n;
	cin >> n;
	vector<int>c;
	rep(i, n) {
		int a;
		cin >> a;
		c.pb(a);
	}
	int q;
	cin >> q;
	vector<int>l, r, v;
	rep(i, q) {
		int a, b, c;
		cin >> a >> b >> c;
		l.pb(a);
		r.pb(b);
		v.pb(c);
	}
	vector<int>ans=distribute_candies(c, l, r, v);
	for(auto i : ans) cout << i << " ";
	cout << '\n';
}*/

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