제출 #851113

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
851113		CSQ31	사탕 분배 (IOI21_candies)	C++17	29 / 100	2133 ms	83344 KiB

candies

#include "candies.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define sz(a) (int)(a.size())
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
typedef long long int ll;
const int MAXN = 2e5+5;
ll mnn[4*MAXN],mxx[4*MAXN],lazy[4*MAXN],ans[MAXN],C[MAXN];
int n,q;
void upd(int v,int l,int r,int tl,int tr,ll val){
	if(l==tl && r==tr){
		lazy[v]+=val;
		mnn[v]+=val;
		mxx[v]+=val;
		return;
	}
	int tm = (tl+tr)/2;
	if(r<=tm)upd(2*v,l,r,tl,tm,val);
	else if(l>tm)upd(2*v+1,l,r,tm+1,tr,val);
	else{
		upd(2*v,l,tm,tl,tm,val);
		upd(2*v+1,tm+1,r,tm+1,tr,val);
	}
	
	mnn[v] = min(mnn[2*v],mnn[2*v+1])+lazy[v];
	mxx[v] = max(mxx[2*v],mxx[2*v+1])+lazy[v];
}
ll mnquery(int v,int l,int r,int tl,int tr){
	if(l>r)return 1e18;
	if(l==tl && r==tr)return mnn[v];
	int tm = (tl+tr)/2;
	return min(mnquery(2*v,l,min(r,tm),tl,tm),
	           mnquery(2*v+1,max(tm+1,l),r,tm+1,tr)) + lazy[v];
}
ll mxquery(int v,int l,int r,int tl,int tr){
	if(l>r)return -1e18;
	if(l==tl && r==tr)return mxx[v];
	int tm = (tl+tr)/2;
	return max(mxquery(2*v,l,min(r,tm),tl,tm),
	           mxquery(2*v+1,max(tm+1,l),r,tm+1,tr)) + lazy[v];
}

vector<pair<int,int>>ch[4*MAXN];
void add(int v,int l,int r,int tl,int tr,int t,ll val){
	if(l>r)return;
	if(l==tl && r==tr){
		ch[v].pb({t+1,val});
		return;
	}
	int tm = (tl+tr)/2;
	add(2*v,l,min(r,tm),tl,tm,t,val);
	add(2*v+1,max(tm+1,l),r,tm+1,tr,t,val);
}
set<pair<int,int>>cur;
ll cursum = 0;
void solve(int v,int tl,int tr){
	for(auto x:ch[v]){
		upd(1,x.fi,q,0,q,x.se);
		cursum+=x.se;
	}
	if(tl==tr){
		int l = 0,r = q;
		//cout<<tl<<" "<<mnn[1]<<" "<<mxx[1]<<'\n';
		while(r>=l){
			int mid = (l+r)/2;
			ll rmn = mnquery(1,mid,q,0,q);
			ll rmx = mxquery(1,mid,q,0,q);
			if(rmx - rmn< C[tl])r = mid-1;
			else l = mid+1;
		}
		if(r==-1){
			ans[tl] = cursum - mnn[1];
			return;
		}
		ll a = mnquery(1,r,q,0,q);
		ll b = mxquery(1,r,q,0,q);
		if(mnquery(1,r,r,0,q) == a)ans[tl] = C[tl] - (b - cursum);
		else ans[tl] = cursum - a; 
		
		for(auto x:ch[v]){
			upd(1,x.fi,q,0,q,-x.se);
			cursum-=x.se;
		}
		return;
	}
	int tm = (tl+tr)/2;
	solve(2*v,tl,tm);
	solve(2*v+1,tm+1,tr);
	for(auto x:ch[v]){
		upd(1,x.fi,q,0,q,-x.se);
		cursum-=x.se;
	}
}
vector<int> distribute_candies(vector<int> c,vector<int> l,vector<int> r,vector<int> v){
    n = sz(c);
    q = sz(l);
    
    for(int i=0;i<n;i++)C[i] = c[i];
    for(int i=0;i<q;i++)add(1,l[i],r[i],0,n-1,i,v[i]);
    solve(1,0,n-1);
    vector<int>tmp(n);
    for(int i=0;i<n;i++)tmp[i] = ans[i];
    return tmp;
}

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