제출 #851094

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
851094		CSQ31	사탕 분배 (IOI21_candies)	C++17	3 / 100	5103 ms	72064 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];
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 0;
	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,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;
void solve(int v,int tl,int tr){
	for(auto x:ch[v])cur.insert(x);
	if(tl==tr){
		vector<ll>p = {0};
		ans[tl] = 0;
		for(auto x:cur){
			ans[tl]+=x.se;
			ans[tl] = max(ans[tl],0LL);
			ans[tl] = min(ans[tl],C[tl]);
		}
		/*
		ll mn = 1e18;
		ll mx = -1e18;
		for(int i=sz(p)-1;i>=0;i--){
			mn = min(mn,p[i]);
			mx = max(mx,p[i]);
			if(mx-mn >= C[tl]){
				if(p[i]==mn)ans[tl] = C[tl] - (mx - p.back());
				else ans[tl] = p.back() - mn;
				break;
			}
			
		}
		if(mx-mn < C[tl])ans[tl] = p.back()-mn;
		* */
		for(auto x:ch[v])cur.erase(x);
		return;
	}
	int tm = (tl+tr)/2;
	solve(2*v,tl,tm);
	solve(2*v+1,tm+1,tr);
	for(auto x:ch[v])cur.erase(x);
}
vector<int> distribute_candies(vector<int> c,vector<int> l,vector<int> r,vector<int> v){
    int n = sz(c);
    int 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: 3 / 3
• Subtask 2: 0 / 8
• Subtask 3: 0 / 27
• Subtask 4: 0 / 29
• Subtask 5: 0 / 33