제출 #1195622

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1195622		nouka28	Fireworks (APIO16_fireworks)	C++20	100 / 100	276 ms	74704 KiB

fireworks

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

// #include<atcoder/all>
// using namespace atcoder;
// using mint=atcoder::modint998244353;

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define rng(i,l,r) for(int i=(l);i<(r);i++)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)
#define rrng(i,l,r) for(int i=(r)-1;i>=(l);i--)

#define fi first
#define se second
#define all(x) (x).begin(),(x).end()

struct fast_io{fast_io(){std::cin.tie(nullptr)->sync_with_stdio(false);}}_;

namespace cplib {

	template <class T>
	struct slope_trick {
		const T INF = std::numeric_limits<T>::max() / 3;

		T min_f;
		std::priority_queue<T, std::vector<T>, std::less<>> L;
		std::priority_queue<T, std::vector<T>, std::greater<>> R;
		T add_l, add_r;

		void push_R(const T& a) { R.push(a - add_r); }
		T top_R() const {
			if (R.empty())
				return INF;
			else
				return R.top() + add_r;
		}

		T pop_R() {
			T val = top_R();
			if (!R.empty()) R.pop();
			return val;
		}

		void push_L(const T& a) { L.push(a - add_l); }

		T top_L() const {
			if (L.empty())
				return -INF;
			else
				return L.top() + add_l;
		}

		T pop_L() {
			T val = top_L();
			if (!L.empty()) L.pop();
			return val;
		}

		size_t size() { return L.size() + R.size(); }

		slope_trick() : min_f(0), add_l(0), add_r(0) {}

		struct Query {
			T lx, rx, min_f;
		};

		// return min f(x)
		Query query() const { return (Query){top_L(), top_R(), min_f}; }

		// f(x)+=a
		void add_all(const T& a) { min_f += a; }

		// add \_
		// f(x) += max(a - x, 0)
		void add_a_minus_x(const T& a) {
			min_f += std::max(T(0), a - top_R());
			push_R(a);
			push_L(pop_R());
		}

		// add _/
		// f(x) += max(x - a, 0)
		void add_x_minus_a(const T& a) {
			min_f += std::max(T(0), top_L() - a);
			push_L(a);
			push_R(pop_L());
		}

		// add \/
		// f(x) += abs(x - a)
		void add_abs(const T& a) {
			add_a_minus_x(a);
			add_x_minus_a(a);
		}

		// \/ -> \_
		// f_{new} (x) = min f(y) (y <= x)
		void clear_right() {
			while (!R.empty()) R.pop();
		}

		// \/ -> _/
		// f_{new} (x) = min f(y) (y >= x)
		void clear_left() {
			while (!L.empty()) L.pop();
		}

		// \/ -> \_/
		// f_{new} (x) = min f(y) (x-b <= y <= x-a)
		void shift(const T& a, const T& b) {
			assert(a <= b);
			add_l += a;
			add_r += b;
		}

		// \/. -> .\/
		// f_{new} (x) = f(x - a)
		void shift(const T& a) { shift(a, a); }

		// destroy L,R
		T get(const T& x) {
			T ret = min_f;
			while (!L.empty()) {
				ret += std::max(T(0), pop_L() - x);
			}
			while (!R.empty()) {
				ret += std::max(T(0), x - pop_R());
			}
			return ret;
		}

		void merge(slope_trick& st) {
			if (st.size() > size()) {
				swap(st.L, L);
				swap(st.R, R);
				swap(st.add_l, add_l);
				swap(st.add_r, add_r);
			}
			while (!st.R.empty()) {
				add_x_minus_a(st.pop_R());
			}
			while (!st.L.empty()) {
				add_a_minus_x(st.pop_L());
			}
			min_f += st.min_f;
		}
	};
	/*
	Slope Trick

	ref :
	- https://ei1333.github.io/library/structure/others/slope-trick.hpp.html
	- https://maspypy.com/slope-trick-1-%E8%A7%A3%E8%AA%AC%E7%B7%A8
	*/
}  // namespace cplib

signed main(){
	int N,M;cin>>N>>M;

	vector<vector<pair<int,int>>> g(N+M);
	rng(i,1,N+M){
		int p,c;cin>>p>>c;p--;
		g[p].push_back({i,c});
	}
	
	vector<cplib::slope_trick<int>> vst(N+M);
	
	rrep(i,N+M){
		if(N<=i){
			vst[i].add_abs(0);
		}

		for(auto&&[e,c]:g[i]){
			int r=vst[e].pop_R();
			while(vst[e].R.size()){
				vst[e].pop_R();
			}
			int l=vst[e].pop_L();
			vst[e].push_L(l+c),vst[e].push_R(r+c);
			vst[i].merge(vst[e]);
		}
	}

	cout<<vst[0].query().min_f<<"\n";
}

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