Submission #453805

#	Time	Username	Problem	Language	Result	Execution time	Memory
453805		lobo_prix	Fireworks (APIO16_fireworks)	C++17	100 / 100	174 ms	76384 KiB

fireworks

#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;

#define int i64
#define FP_EPS 1e-11
#define COUT_FP 11
// #define CPP20 1

#define pushb push_back
#define pushf push_front
#define popb pop_back
#define popf pop_front
#define empl emplace
#define emplb emplace_back
#define emplf emplace_front
#define fi first
#define se second
#define mkp make_pair
#define mkt make_tuple
#define cxp constexpr
#define lb lower_bound
#define ub upper_bound
#define reduce accumulate
#define itos to_string
using i64=long long;using u64=unsigned long long;using f64=double;
using pint=pair<int,int>;using tint=tuple<int,int,int>;
template<class T>using Str=basic_string<T>;

//Handy Funcs
template<class T>int sz(const T& x){return x.size();}
template<class T>cxp T inf(){return numeric_limits<T>::max()/2;}
int divc(int a,int b){if(b<0)a=-a,b=-b;return (a>0)?(a+b-1)/b:a/b;}
int divf(int a,int b){if(b<0)a=-a,b=-b;return (a>0)?a/b:(a-b+1)/b;}
cxp int lg2f(int x){return 63-__builtin_clzll(x);}
cxp int lg2c(int x){return 64-__builtin_clzll(x-1);}
template<class T>inline T sq(T x){return x*x;}
bool assmin(auto& a,auto&& b){return a>b?a=b,true:false;}
bool assmax(auto& a,auto&& b){return a<b?a=b,true:false;}
int argmin(const auto& a){return min_element(a.begin(),a.end())-a.begin();}
int argmax(const auto& a){return max_element(a.begin(),a.end())-a.begin();}

void WARN(bool cond,const char* str){
	#if DEBUG
	static set<const char*> z;
	if(cond&&!z.count(str))z.insert(str),cerr<<"[WARN] "<<str<<endl;
	#endif
}

template<class T, class P=
#if CPP20
conditional_t<is_same<bool,T>::value,deque<T>,vector<T>>>
#else
vector<T>>
#endif
struct Arr:public P{
	Arr():Arr(0){}
	explicit Arr(signed n,T init=T()):P(n,init){}
	Arr(initializer_list<T>il):P(il){}
#ifdef CPP20
	Arr(auto its, auto ite):P(its,ite){}
#endif
	T& operator[](signed i){
		WARN(i<0,"Negative Index Found");
		return P::operator[](i>=0?i:i+this->size());
	}
	const T& operator[](signed i)const{return P::operator[](i>=0?i:i+this->size());}
	T& at(signed i){return *this[i];}
	const T& at(signed i)const{return *this[i];}
};
template<class... A> auto ARR(auto n,A&&... a)
{if constexpr(!sizeof...(a)) return n; else return Arr(n,ARR(a...));}

//Monoid
#ifdef CPP20
template<class T, auto _f=[](T x,T y){return x+y;}, T _id=0>
struct Monoid{static cxp auto f=_f,id=_id;};
template<class T, class M=Monoid<T>>
Arr<T> cumf(const Arr<T>& a){
	Arr<T> b(sz(a)+1,M::id);
	for(int i=0;i<sz(a);i++)
		b[i]=M::f(b[i-1],a[i]);
	return b;
}
#endif

//Func Exts
#define RETT(...) __VA_ARGS__
#define func(RetT,fname,...) function<RetT(__VA_ARGS__)> fname=[&](__VA_ARGS__)->RetT
#define lam(expr,...) [&](__VA_ARGS__){return expr;}

#define PQ std::priority_queue
template<class T>using PQMax=PQ<T>;
template<class T>using PQMin=PQ<T,vector<T>,greater<T>>;

//Consts
const f64 pi=acosl(-1),eps=FP_EPS;
const int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};

//Pre-runs
#if !(DEBUG)
auto __PR1=(ios::sync_with_stdio(0),cin.tie(0),cout.tie(0));
#endif
auto& __PR2=(cout<<fixed<<setprecision(COUT_FP));
//

#define FASTIO

//INPUT
struct FastCIN{
	static const int SZ=1<<24;
	unsigned cnt=0;char a[SZ+1],*p;
	FastCIN(){preload();}
	void tie(int x){}
	int preload(){return cnt=cin.read(p=a,SZ).gcount();}
	inline char pop(){if(!cnt)preload(); return cnt>0?cnt--,*p++:0;}
	inline char get(){if(!cnt)preload(); return cnt>0?*p:0;}
	void ignore_wsc(){while(get()==' '||get()=='\n')pop();}
	operator bool(){return get();}
	template<class T>FastCIN& operator>>(T& n){ignore_wsc();n=0;char neg=false;if(get()=='-')neg=true,pop();while('0'<=get()&&get()<='9')n=n*10+pop()-'0';if(neg)n*=-1;return *this;}//int,i64,Mod<mod>
	FastCIN& operator>>(char& c){ignore_wsc();c=pop();return *this;}
	FastCIN& operator>>(string& s){ignore_wsc();s.clear();while(get()!=' '&&get()!='\n'&&get())s.pushb(pop());return *this;}
	FastCIN& operator>>(f64& n){ignore_wsc();string s;while(('0'<=get()&&get()<='9')||get()=='.'||get()=='-')s.pushb(pop());n=stod(s);return *this;}
	template<class T> FastCIN& operator>>(Arr<T>& a){for(auto& i:a)*this>>i;return *this;}
	template<class T,class U> FastCIN& operator>>(pair<T,U>& a){*this>>a.fi>>a.se;return *this;}
};

struct TokCIN:public FastCIN{
	static TokCIN* x;
	static TokCIN* instance(){return !x?x=new TokCIN():x;}
	template<class T=i64>T tok(){T x;operator>>(x);return x;}
	template<class T=i64>Arr<T> toks(int n){Arr<T> a(n);for(auto& i:a)operator>>(i);return a;}
	template<class... A> void _read(A&...a){((operator>>(a)),...);}
};
TokCIN* TokCIN::x;
#define cin (*TokCIN::instance())
#define READ(T,...) T __VA_ARGS__;cin._read(__VA_ARGS__);

//OUTPUT
template<class T> ostream& operator<<(ostream& s,const Arr<T>& a){for(auto i:a)cout<<i<<' ';return s;}
template<class T> ostream& operator<<(ostream& o,const pair<T,T>& x){return o<<x.fi<<' '<<x.se;}
template<class... A> void PRINT(A...a){((cout<<a<<' '),...,(cout<<endl));}

//

//NOTE: f(x)=min{f(x+i),i<a}+|x-k|+m -> pf(k)sf(k)ab(-a,m)
//NOTE: sf_inc에 답구하는게 들어있어서, 반드시 한 연산에 대해 pf_dec->sf_inc순서로 호출
struct LeftHull{
	void pf_dec(int x){pq.empl(x-bias);}//x이하의 기울기들 -1
	int sf_inc(int x){//x이상의 기울기들 +1, pop된 원소 반환(Right Hull관리에 사용됨)
		if(pq.empty() or argmin()<=x)return x;
		ans+=argmin()-x;//이 경우 최솟값이 증가함
		pq.empl(x-bias);//x 이하 -1
		int r=argmin();pq.pop();//전체 +1
		return r;
	}
	void add_bias(int x,int y){bias+=x;ans+=y;}//그래프 x축 평행이동
	int minval(){return ans;}//최소값
	int argmin(){return pq.empty()?-inf<int>():pq.top()+bias;}//최소값 x좌표

	void operator+=(LeftHull& a){
		ans+=a.ans;
		while(sz(a.pq))pf_dec(a.argmin()), a.pq.pop();
	}
	int size()const{return sz(pq);}
	
// private:
	PQMax<int> pq;
	int ans=0,bias=0;
};

//NOTE: f(x)=min{f(x+i),a<i<b}+|x-k|+m -> pf(k)sf(k)ab(-a,b,m)
struct SlopeTrick{
	void pf_dec(int x){l.pf_dec(-r.sf_inc(-x));}
	void sf_inc(int x){r.pf_dec(-l.sf_inc(x));}
	void add_bias(int lx,int rx,int y){l.add_bias(lx,0),r.add_bias(-rx,0),ans+=y;}
	int minval(){return ans+l.minval()+r.minval();}
	pint argmin(){return {l.argmin(),-r.argmin()};}
	void operator+=(SlopeTrick& a){
		while(sz(a.l.pq))
			pf_dec(a.l.argmin()),a.l.pq.pop();
		l.ans+=a.l.ans;
		
		while(sz(a.r.pq))
			sf_inc(-a.r.argmin()),a.r.pq.pop();
		r.ans+=a.r.ans;
		
		ans+=a.ans;
	}
	int size()const{return l.size()+r.size();}
// private:
	LeftHull l,r;
	int ans=0;
};

//LeftHull 역추적 방법: 스텝i의 argmin값을 am(i)라고 하자. 스텝n부터 스텝1까지 ans[i]=min(ans[i+1],am(i))하면 된다. 아래는 증명..은 아니고 간략한 이유
//am(i)<=ans[i+1]일때: ans[i]=am(i)
//x[i]>ans[i+1]일때: ans[i]=ans[i+1] 왜냐하면 f(i,a)는 a<x[i]에서 감소함수이므로 가능한 최대로 오른쪽으로 붙은 ans[i+1]이 최적.
//스텝i에서 add_bias(k,0)한다면 간격제한k가 있는것이므로 ans[i]=min(ans[i+1]-k,x[i])으로 수정.
//LR Hull 역추적은 케이스나눠서 위 방법을 확장하면 될듯

// Random
mt19937 _rng(i64(new int) ^ time(0));
int rd() {
	static uniform_int_distribution<int> dist(0, inf<int>());
	return dist(_rng);
}
int rd(int e) { return rd() % e; }
int rd(int s, int e) { return rd() % (e - s) + s; }
f64 rdf() {
	static uniform_real_distribution<f64> dist(0, 1);
	return dist(_rng);
}
void shuffle(auto is, auto ie) { shuffle(is, ie, _rng); }
#define endl '\n'


signed main(){
	READ(int,n,m);
	Arr<int> p(n+m),c(n+m);
	for(int i=1;i<n;i++){
		cin>>p[i]>>c[i];
		p[i]--;
	}
	Arr<SlopeTrick> dp(n+m);
	for(int i=n;i<n+m;i++){
		cin>>p[i]>>c[i];
		p[i]--;

		dp[i].pf_dec(c[i]);
		dp[i].sf_inc(c[i]);

		dp[p[i]]+=dp[i];
	}
	for(int i=n-1;i;i--){
		auto [lx,rx]=dp[i].argmin();
		dp[i].l.pq.pop();
		dp[i].r.pq=PQMax<int>();

		dp[i].pf_dec(lx+c[i]);
		dp[i].sf_inc(rx+c[i]);

		if(sz(dp[p[i]])>sz(dp[i]))dp[p[i]]+=dp[i];
		else{
			dp[i]+=dp[p[i]];
			swap(dp[i],dp[p[i]]);
		}
	}
	cout<<dp[0].minval()<<endl;
}

Compilation message (stderr)

fireworks.cpp:38:13: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   38 | bool assmin(auto& a,auto&& b){return a>b?a=b,true:false;}
      |             ^~~~
fireworks.cpp:38:21: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   38 | bool assmin(auto& a,auto&& b){return a>b?a=b,true:false;}
      |                     ^~~~
fireworks.cpp:39:13: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   39 | bool assmax(auto& a,auto&& b){return a<b?a=b,true:false;}
      |             ^~~~
fireworks.cpp:39:21: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   39 | bool assmax(auto& a,auto&& b){return a<b?a=b,true:false;}
      |                     ^~~~
fireworks.cpp:40:18: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   40 | int argmin(const auto& a){return min_element(a.begin(),a.end())-a.begin();}
      |                  ^~~~
fireworks.cpp:41:18: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   41 | int argmax(const auto& a){return max_element(a.begin(),a.end())-a.begin();}
      |                  ^~~~
fireworks.cpp:71:31: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   71 | template<class... A> auto ARR(auto n,A&&... a)
      |                               ^~~~
fireworks.cpp:214:14: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
  214 | void shuffle(auto is, auto ie) { shuffle(is, ie, _rng); }
      |              ^~~~
fireworks.cpp:214:23: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
  214 | void shuffle(auto is, auto ie) { shuffle(is, ie, _rng); }
      |                       ^~~~

• Subtask 1: 7 / 7
• Subtask 2: 19 / 19
• Subtask 3: 29 / 29
• Subtask 4: 45 / 45