제출 #504670

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
504670		arthur_nascimento	사탕 분배 (IOI21_candies)	C++17	40 / 100	4726 ms	70872 KiB

candies

#include "candies.h"
 
#include <cassert>
#include <cstdio>
#include <vector>
#include <bits/stdc++.h>
using namespace std;
 
#define maxn 200200
#define mid ((ini+fim)/2)
#define pb push_back
#define ll long long
#define search iwfew
#define debug 
 
ll T[4*maxn];
ll mn[4*maxn];
ll mx[4*maxn];
int pos_mn[4*maxn];
int pos_mx[4*maxn];
 
ll lazy[4*maxn];
 
int n,q;
 
void refresh(int ini,int fim,int p){
 
	if(ini < fim){
		lazy[2*p] += lazy[p];
		lazy[2*p+1] += lazy[p];
	}
 
	mn[p] += lazy[p];
	mx[p] += lazy[p];
 
	lazy[p] = 0;
	
}
 
void merge(int ini,int fim,int p){
	mx[p] = max(mx[2*p],mx[2*p+1]);
	mn[p] = min(mn[2*p],mn[2*p+1]);
	pos_mn[p] = pos_mn[2*p];
	if(mn[2*p+1] < mn[2*p]) pos_mn[p] = pos_mn[2*p+1];
	pos_mx[p] = pos_mx[2*p];
	if(mx[2*p+1] > mx[2*p]) pos_mx[p] = pos_mx[2*p+1];
	T[p] = mx[p] - mn[p];
	debug("pos_mx[%d] := %d\n",p,pos_mx[p]);
	
}
 
void bd(int ini,int fim,int p){
	if(ini == fim){
		pos_mn[p] = ini;
		pos_mx[p] = ini;
		return;
	}
	bd(ini,mid,2*p);
	bd(mid+1,fim,2*p+1);
	pos_mn[p] = ini;
	pos_mx[p] = ini;
}
 
int search(int ini,int fim,int p,ll d,ll mnr=0,ll mxr=0,ll hasr=0){
 
	refresh(ini,fim,p);
 
	if(ini == fim) return ini;
 
	refresh(mid+1,fim,2*p+1);
	merge(ini,fim,p);
 
	ll gapR = T[2*p+1];
	if(hasr) gapR = max(gapR, mxr - mn[2*p+1]);
	if(hasr) gapR = max(gapR, mx[2*p+1] - mnr);
 
	if(gapR > d) return search(mid+1,fim,2*p+1,d,mnr,mxr,hasr);
 
	ll mn_ = mn[2*p+1]; if(hasr) mn_ = min(mn_, mnr);
	ll mx_ = mx[2*p+1]; if(hasr) mx_ = max(mx_, mxr);
 
	return search(ini,mid,2*p,d,mn_,mx_,1);
	
}
 
ll vm, vM;
int pm, pM;
 
void qr(int ini,int fim,int p,int l,int r){
 
	debug("qr %d~%d p %d\n",ini,fim,p);
	refresh(ini,fim,p);
 
	if(ini > r || fim < l) return;
	if(ini >= l && fim <= r){
 
		if(mn[p] < vm){
			vm = mn[p];
			pm = pos_mn[p];
		}
 
		debug("mx %lld po %d\n",mx[p],pos_mx[p]);
 
		if(mx[p] > vM){
			vM = mx[p];
			pM = pos_mx[p];
		}
 
		return;
	}
 
	qr(ini,mid,2*p,l,r);
	qr(mid+1,fim,2*p+1,l,r);
 
	merge(ini,fim,p);
}
 
int get_min(int a){
	vm = 1e18;
	vM = -1e18;
	qr(0,q,1,a,q);
	return pm;
}
 
int get_max(int a){ 
	vm = 1e18;
	vM = -1e18;
	qr(0,q,1,a,q);
	debug("mx (%d) = %d\n",a,pM);
	return pM;
}
 
ll get(int ini,int fim,int p,int pos){
	refresh(ini,fim,p);
	if(ini > pos || fim < pos) return 0;
	if(ini == fim) return mx[p];
	ll ret = get(ini,mid,2*p,pos) + get(mid+1,fim,2*p+1,pos);
	merge(ini,fim,p);
	return ret;
}
 
void upd(int ini,int fim,int p,int l,int r,int x){
 
	refresh(ini,fim,p);
 
	if(l > fim || r < ini) return;
 
	if(ini >= l && fim <= r){
		lazy[p] += x;
		refresh(ini,fim,p);
		return;
	}
 
	upd(ini,mid,2*p,l,r,x);
	upd(mid+1,fim,2*p+1,l,r,x);
 
	merge(ini,fim,p);
 
}
 
 
 
vector<int> Ti[4*maxn];
 
void updi(int ini,int fim,int p,int a,int b,int k){
	if(ini > b) return;
	if(fim < a) return;
	if(ini >= a && fim <= b){
		Ti[p].pb(k);
		return;
	}
	updi(ini,mid,2*p,a,b,k);
	updi(mid+1,fim,2*p+1,a,b,k);
}
 
vector<int> ans;
 
vector<int> l,r,add,cap;
 
void go(int ini,int fim,int p){
 
	debug("go %d~%d\n",ini,fim);
 
	for(int a : Ti[p]){
		upd(0,q,1,a+1,q,add[a]);
		debug("add %d at %d\n",add[a],a);
	}
	
	if(ini == fim){
 
		ll c = cap[ini];
 
		int beg = 0;
 
		debug("qry %d cap %d\n",ini,c);
 
		if(T[1] > c)
			beg = 1 + search(0,q,1,c);
 
		beg = max(beg,pos_mn[1]);
 
		ll delta = get(0,q,1,q) - get(0,q,1,beg);
 
		debug("get %d = %lld\n",q,get(0,q,1,q));
		debug("get %d = %lld\n",beg-1,get(0,q,1,beg-1));
		debug("get %d = %lld\n",beg,get(0,q,1,beg));
 
		debug("T[1] = %d, beg = %d, delta = %lld\n\n",T[1],beg,delta);
 
		if(beg > 0){
 
			if(get(0,q,1,beg-1) >= get(0,q,1,beg)) {
 
				beg = get_min(beg);
				delta = get(0,q,1,q) - get(0,q,1,beg);
				ans[ini] = delta;
 
			}
 
			else {
 
				beg = get_max(beg);
				delta = get(0,q,1,q) - get(0,q,1,beg);
				ans[ini] = c + delta;
			
			}
			
		}
 
		else ans[ini] = delta;
 
	//	if(delta == 0 && beg > 0 && get(0,q,1,beg-1) > get(0,q,1,beg)) ans[ini] = 0;
	
	}
 
	if(ini < fim) go(ini,mid,2*p);
	if(ini < fim) go(mid+1,fim,2*p+1);
 
	for(int a : Ti[p]){
		upd(0,q,1,a+1,q,-add[a]);
		debug("rem %d at %d\n",add[a],a);
	}
}
 
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> L,
                                    std::vector<int> R, std::vector<int> v) {
    n = c.size();
    q = L.size();
 
	cap = c;
	l = L;
	r = R;
	add = v;
    
	for(int i=0;i<q;i++)
		updi(0,n-1,1,l[i],r[i],i);
 
	bd(0,q,1);		
 
	for(int i=0;i<n;i++) ans.pb(0);
 
	go(0,n-1,1);
 
    return ans;
}

컴파일 시 표준 에러 (stderr) 메시지

candies.cpp: In function 'void merge(int, int, int)':
candies.cpp:48:8: warning: left operand of comma operator has no effect [-Wunused-value]
   48 |  debug("pos_mx[%d] := %d\n",p,pos_mx[p]);
      |        ^~~~~~~~~~~~~~~~~~~~
candies.cpp:48:39: warning: right operand of comma operator has no effect [-Wunused-value]
   48 |  debug("pos_mx[%d] := %d\n",p,pos_mx[p]);
      |                                       ^
candies.cpp: In function 'void qr(int, int, int, int, int)':
candies.cpp:91:8: warning: left operand of comma operator has no effect [-Wunused-value]
   91 |  debug("qr %d~%d p %d\n",ini,fim,p);
      |        ^~~~~~~~~~~~~~~~~
candies.cpp:91:30: warning: right operand of comma operator has no effect [-Wunused-value]
   91 |  debug("qr %d~%d p %d\n",ini,fim,p);
      |                              ^~~
candies.cpp:91:34: warning: right operand of comma operator has no effect [-Wunused-value]
   91 |  debug("qr %d~%d p %d\n",ini,fim,p);
      |                                  ^
candies.cpp:102:9: warning: left operand of comma operator has no effect [-Wunused-value]
  102 |   debug("mx %lld po %d\n",mx[p],pos_mx[p]);
      |         ^~~~~~~~~~~~~~~~~
candies.cpp:102:31: warning: right operand of comma operator has no effect [-Wunused-value]
  102 |   debug("mx %lld po %d\n",mx[p],pos_mx[p]);
      |                           ~~~~^
candies.cpp: In function 'int get_max(int)':
candies.cpp:129:8: warning: left operand of comma operator has no effect [-Wunused-value]
  129 |  debug("mx (%d) = %d\n",a,pM);
      |        ^~~~~~~~~~~~~~~~
candies.cpp:129:27: warning: right operand of comma operator has no effect [-Wunused-value]
  129 |  debug("mx (%d) = %d\n",a,pM);
      |                           ^~
candies.cpp: In function 'void go(int, int, int)':
candies.cpp:182:8: warning: left operand of comma operator has no effect [-Wunused-value]
  182 |  debug("go %d~%d\n",ini,fim);
      |        ^~~~~~~~~~~~
candies.cpp:182:25: warning: right operand of comma operator has no effect [-Wunused-value]
  182 |  debug("go %d~%d\n",ini,fim);
      |                         ^~~
candies.cpp:186:9: warning: left operand of comma operator has no effect [-Wunused-value]
  186 |   debug("add %d at %d\n",add[a],a);
      |         ^~~~~~~~~~~~~~~~
candies.cpp:195:9: warning: left operand of comma operator has no effect [-Wunused-value]
  195 |   debug("qry %d cap %d\n",ini,c);
      |         ^~~~~~~~~~~~~~~~~
candies.cpp:195:31: warning: right operand of comma operator has no effect [-Wunused-value]
  195 |   debug("qry %d cap %d\n",ini,c);
      |                               ^
candies.cpp:204:9: warning: left operand of comma operator has no effect [-Wunused-value]
  204 |   debug("get %d = %lld\n",q,get(0,q,1,q));
      |         ^~~~~~~~~~~~~~~~~
candies.cpp:204:40: warning: right operand of comma operator has no effect [-Wunused-value]
  204 |   debug("get %d = %lld\n",q,get(0,q,1,q));
      |                                        ^
candies.cpp:205:9: warning: left operand of comma operator has no effect [-Wunused-value]
  205 |   debug("get %d = %lld\n",beg-1,get(0,q,1,beg-1));
      |         ^~~~~~~~~~~~~~~~~
candies.cpp:205:30: warning: right operand of comma operator has no effect [-Wunused-value]
  205 |   debug("get %d = %lld\n",beg-1,get(0,q,1,beg-1));
      |                           ~~~^~
candies.cpp:206:9: warning: left operand of comma operator has no effect [-Wunused-value]
  206 |   debug("get %d = %lld\n",beg,get(0,q,1,beg));
      |         ^~~~~~~~~~~~~~~~~
candies.cpp:206:44: warning: right operand of comma operator has no effect [-Wunused-value]
  206 |   debug("get %d = %lld\n",beg,get(0,q,1,beg));
      |                                            ^
candies.cpp:208:9: warning: left operand of comma operator has no effect [-Wunused-value]
  208 |   debug("T[1] = %d, beg = %d, delta = %lld\n\n",T[1],beg,delta);
      |         ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
candies.cpp:208:52: warning: right operand of comma operator has no effect [-Wunused-value]
  208 |   debug("T[1] = %d, beg = %d, delta = %lld\n\n",T[1],beg,delta);
      |                                                 ~~~^
candies.cpp:208:58: warning: right operand of comma operator has no effect [-Wunused-value]
  208 |   debug("T[1] = %d, beg = %d, delta = %lld\n\n",T[1],beg,delta);
      |                                                          ^~~~~
candies.cpp:241:9: warning: left operand of comma operator has no effect [-Wunused-value]
  241 |   debug("rem %d at %d\n",add[a],a);
      |         ^~~~~~~~~~~~~~~~

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