oj.uz

Submission #453804

# Submission time Handle Problem Language Result Execution time Memory
453804 2021-08-04T23:09:07 Z lobo_prix Fireworks (APIO16_fireworks) C++17
55 / 100
 2000 ms 248440 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){
		
		// r+=a.r;
		while(sz(a.l.pq))
			pf_dec(a.l.argmin()),a.l.pq.pop();
		l.ans+=a.l.ans;
		
		// l+=a.l;
		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);
	// int n=200000,m=100000;
	Arr<int> p(n+m),c(n+m);
	for(int i=1;i<n;i++){
		cin>>p[i]>>c[i];
		p[i]--;
		// p[i]=rd(i);
		// c[i]=rd(10'0000'0000)+1;
	}
	Arr<SlopeTrick> dp(n+m);
	for(int i=n;i<n+m;i++){
		cin>>p[i]>>c[i];
		p[i]--;
		// p[i]=rd(n);
		// c[i]=rd(10'0000'0000)+1;

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

		dp[p[i]]+=dp[i];
	}
	for(int i=n-1;i;i--){
		// dp[i].add_bias(0,0,c[i]);z
		if(dp[i].size()==0)continue;
		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]);

		dp[p[i]]+=dp[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:217:14: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
  217 | void shuffle(auto is, auto ie) { shuffle(is, ie, _rng); }
      |              ^~~~
fireworks.cpp:217:23: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
  217 | 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 344 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 340 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

Subtask #2
19.0 / 19.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 0 ms 332 KB Output is correct
4 Correct 1 ms 344 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 336 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 1 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 344 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 340 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 0 ms 332 KB Output is correct
12 Correct 0 ms 332 KB Output is correct
13 Correct 0 ms 332 KB Output is correct
14 Correct 1 ms 344 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 336 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 1 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 460 KB Output is correct
31 Correct 2 ms 716 KB Output is correct
32 Correct 2 ms 844 KB Output is correct
33 Correct 4 ms 1100 KB Output is correct
34 Correct 5 ms 1484 KB Output is correct
35 Correct 10 ms 2252 KB Output is correct
36 Correct 9 ms 2224 KB Output is correct
37 Correct 8 ms 2220 KB Output is correct
38 Correct 20 ms 3660 KB Output is correct
39 Correct 10 ms 2508 KB Output is correct
40 Correct 2 ms 1356 KB Output is correct
41 Correct 2 ms 1356 KB Output is correct
42 Correct 2 ms 1356 KB Output is correct
43 Correct 211 ms 32012 KB Output is correct
44 Correct 167 ms 23860 KB Output is correct
45 Correct 166 ms 23724 KB Output is correct
46 Correct 3 ms 1484 KB Output is correct
47 Correct 3 ms 1552 KB Output is correct
48 Correct 3 ms 1356 KB Output is correct
49 Correct 3 ms 1484 KB Output is correct
50 Correct 3 ms 1228 KB Output is correct
51 Correct 3 ms 1304 KB Output is correct
52 Correct 7 ms 1868 KB Output is correct
53 Correct 4 ms 1484 KB Output is correct
54 Correct 3 ms 1356 KB Output is correct

Subtask #4
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 344 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 340 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 0 ms 332 KB Output is correct
12 Correct 0 ms 332 KB Output is correct
13 Correct 0 ms 332 KB Output is correct
14 Correct 1 ms 344 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 336 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 1 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 460 KB Output is correct
31 Correct 2 ms 716 KB Output is correct
32 Correct 2 ms 844 KB Output is correct
33 Correct 4 ms 1100 KB Output is correct
34 Correct 5 ms 1484 KB Output is correct
35 Correct 10 ms 2252 KB Output is correct
36 Correct 9 ms 2224 KB Output is correct
37 Correct 8 ms 2220 KB Output is correct
38 Correct 20 ms 3660 KB Output is correct
39 Correct 10 ms 2508 KB Output is correct
40 Correct 2 ms 1356 KB Output is correct
41 Correct 2 ms 1356 KB Output is correct
42 Correct 2 ms 1356 KB Output is correct
43 Correct 211 ms 32012 KB Output is correct
44 Correct 167 ms 23860 KB Output is correct
45 Correct 166 ms 23724 KB Output is correct
46 Correct 3 ms 1484 KB Output is correct
47 Correct 3 ms 1552 KB Output is correct
48 Correct 3 ms 1356 KB Output is correct
49 Correct 3 ms 1484 KB Output is correct
50 Correct 3 ms 1228 KB Output is correct
51 Correct 3 ms 1304 KB Output is correct
52 Correct 7 ms 1868 KB Output is correct
53 Correct 4 ms 1484 KB Output is correct
54 Correct 3 ms 1356 KB Output is correct
55 Correct 48 ms 8944 KB Output is correct
56 Correct 474 ms 60500 KB Output is correct
57 Correct 952 ms 117528 KB Output is correct
58 Correct 1104 ms 143440 KB Output is correct
59 Execution timed out 2100 ms 248440 KB Time limit exceeded
60 Halted 0 ms 0 KB -