oj.uz

Submission #453805

# Submission time Handle Problem Language Result Execution time Memory
453805 2021-08-04T23:11:23 Z lobo_prix Fireworks (APIO16_fireworks) C++17
100 / 100
 174 ms 76384 KB 
#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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 0 ms 332 KB Output is correct
10 Correct 0 ms 332 KB Output is correct

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 0 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 332 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 0 ms 332 KB Output is correct
10 Correct 0 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 0 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 0 ms 332 KB Output is correct
15 Correct 0 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 1 ms 332 KB Output is correct
22 Correct 1 ms 332 KB Output is correct
23 Correct 1 ms 332 KB Output is correct
24 Correct 0 ms 332 KB Output is correct
25 Correct 1 ms 332 KB Output is correct
26 Correct 1 ms 332 KB Output is correct
27 Correct 1 ms 332 KB Output is correct
28 Correct 1 ms 332 KB Output is correct
29 Correct 1 ms 332 KB Output is correct
30 Correct 1 ms 332 KB Output is correct
31 Correct 1 ms 460 KB Output is correct
32 Correct 1 ms 588 KB Output is correct
33 Correct 1 ms 716 KB Output is correct
34 Correct 2 ms 844 KB Output is correct
35 Correct 2 ms 972 KB Output is correct
36 Correct 2 ms 1100 KB Output is correct
37 Correct 3 ms 1228 KB Output is correct
38 Correct 3 ms 1228 KB Output is correct
39 Correct 3 ms 1228 KB Output is correct
40 Correct 2 ms 972 KB Output is correct
41 Correct 2 ms 876 KB Output is correct
42 Correct 2 ms 972 KB Output is correct
43 Correct 3 ms 1356 KB Output is correct
44 Correct 3 ms 1228 KB Output is correct
45 Correct 3 ms 1228 KB Output is correct
46 Correct 3 ms 1484 KB Output is correct
47 Correct 3 ms 1484 KB Output is correct
48 Correct 3 ms 1276 KB Output is correct
49 Correct 3 ms 1356 KB Output is correct
50 Correct 2 ms 1228 KB Output is correct
51 Correct 3 ms 1228 KB Output is correct
52 Correct 3 ms 1356 KB Output is correct
53 Correct 3 ms 1356 KB Output is correct
54 Correct 3 ms 1356 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 0 ms 332 KB Output is correct
10 Correct 0 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 0 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 0 ms 332 KB Output is correct
15 Correct 0 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 1 ms 332 KB Output is correct
22 Correct 1 ms 332 KB Output is correct
23 Correct 1 ms 332 KB Output is correct
24 Correct 0 ms 332 KB Output is correct
25 Correct 1 ms 332 KB Output is correct
26 Correct 1 ms 332 KB Output is correct
27 Correct 1 ms 332 KB Output is correct
28 Correct 1 ms 332 KB Output is correct
29 Correct 1 ms 332 KB Output is correct
30 Correct 1 ms 332 KB Output is correct
31 Correct 1 ms 460 KB Output is correct
32 Correct 1 ms 588 KB Output is correct
33 Correct 1 ms 716 KB Output is correct
34 Correct 2 ms 844 KB Output is correct
35 Correct 2 ms 972 KB Output is correct
36 Correct 2 ms 1100 KB Output is correct
37 Correct 3 ms 1228 KB Output is correct
38 Correct 3 ms 1228 KB Output is correct
39 Correct 3 ms 1228 KB Output is correct
40 Correct 2 ms 972 KB Output is correct
41 Correct 2 ms 876 KB Output is correct
42 Correct 2 ms 972 KB Output is correct
43 Correct 3 ms 1356 KB Output is correct
44 Correct 3 ms 1228 KB Output is correct
45 Correct 3 ms 1228 KB Output is correct
46 Correct 3 ms 1484 KB Output is correct
47 Correct 3 ms 1484 KB Output is correct
48 Correct 3 ms 1276 KB Output is correct
49 Correct 3 ms 1356 KB Output is correct
50 Correct 2 ms 1228 KB Output is correct
51 Correct 3 ms 1228 KB Output is correct
52 Correct 3 ms 1356 KB Output is correct
53 Correct 3 ms 1356 KB Output is correct
54 Correct 3 ms 1356 KB Output is correct
55 Correct 6 ms 2904 KB Output is correct
56 Correct 24 ms 10140 KB Output is correct
57 Correct 44 ms 16976 KB Output is correct
58 Correct 58 ms 21596 KB Output is correct
59 Correct 86 ms 28864 KB Output is correct
60 Correct 104 ms 38420 KB Output is correct
61 Correct 125 ms 44092 KB Output is correct
62 Correct 141 ms 48568 KB Output is correct
63 Correct 171 ms 57776 KB Output is correct
64 Correct 174 ms 60736 KB Output is correct
65 Correct 66 ms 45252 KB Output is correct
66 Correct 65 ms 45252 KB Output is correct
67 Correct 68 ms 45384 KB Output is correct
68 Correct 131 ms 65932 KB Output is correct
69 Correct 151 ms 65088 KB Output is correct
70 Correct 155 ms 65076 KB Output is correct
71 Correct 173 ms 76148 KB Output is correct
72 Correct 173 ms 76384 KB Output is correct
73 Correct 150 ms 72868 KB Output is correct
74 Correct 155 ms 73328 KB Output is correct
75 Correct 151 ms 71412 KB Output is correct
76 Correct 153 ms 71848 KB Output is correct
77 Correct 159 ms 68732 KB Output is correct
78 Correct 159 ms 68392 KB Output is correct
79 Correct 136 ms 66020 KB Output is correct