Submission #1175832

---

Source Code Expand

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){return o<<"("<<p.fs<<","<<p.sc<<")";}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){o<<"sz = "<<vc.size()<<endl<<"[";for(const T& v:vc) o<<v<<",";o<<"]";return o;}

template<class Handler>
struct segtree_lazy{
	using val_t = typename Handler::val_t;
	using opr_t = typename Handler::opr_t;
	int N;
	vector<val_t> val;
	vector<opr_t> lazy;
	segtree_lazy(){}
	segtree_lazy(int n){init(n);}
	segtree_lazy(const vector<val_t>& vc){init(vc);}
	void init(int n){
		N=1;
		while(N<n) N*=2;
		val .assign(N*2,val_t::e);
		lazy.assign(N*2,opr_t::e);
	}
	void init(const vector<val_t>& vc){
		int n = vc.size();
		N=1;
		while(N<n) N*=2;
		val .assign(N*2,val_t::e);
		rep(i,n) val[i+N] = vc[i];
		for(int i=N-1;i>0;i--) val[i] = val[i*2] + val[i*2+1];
		lazy.assign(N*2,opr_t::e);
	}
	val_t realvalue(int k,int l,int r){
//		return Handler::act(lazy[k],val[k]);
		return Handler::act(lazy[k],val[k],k,l,r);
	}

	val_t calc(int a,int b,int l=0,int r=-1,int k=1){	//query_calc
		if(r==-1) r=N;
		if(b<=l||r<=a) return val_t::e;
		if(a<=l&&r<=b) return realvalue(k,l,r);
		propagate(l,r,k);
		val_t ret = calc(a,b,l,(l+r)/2,k*2) + calc(a,b,(l+r)/2,r,k*2+1);
		val[k] = realvalue(k*2,l,(l+r)/2) + realvalue(k*2+1,(l+r)/2,r);
		return ret;

	}
//	val_t calc_leftassoc(){}
	void update(int a,int b,const opr_t &x,int l=0,int r=-1,int k=1){	//query_update
		if(r==-1) r=N;
		if(b<=l||r<=a) return;
		if(a<=l&&r<=b){
			Handler::setg2fg(x,lazy[k]);
			return;
		}
		propagate(l,r,k);
		update(a,b,x,l,(l+r)/2,k*2);
		update(a,b,x,(l+r)/2,r,k*2+1);
		val[k] = realvalue(k*2,l,(l+r)/2) + realvalue(k*2+1,(l+r)/2,r);
	}
	void propagate(int l,int r,int k){	//opr_child -> opr_parent * opr_child		parent after child
		Handler::setg2fg(lazy[k],lazy[k*2  ]);
		Handler::setg2fg(lazy[k],lazy[k*2+1]);
		lazy[k] = opr_t::e;
	}

	int getval(int m){
		return calc(m,m+1).x;
	}
	void add(int l,int r,long long v){
//		printf("add %d,%d, +=%lld\n",l,r,v);
		update(l,r,opr_t(true,v));
	}
	void assign(int l,int r,long long v){
		update(l,r,opr_t(false,v));
	}
};

struct handler3{
	using ll = long long;
	/*
		range assign
		range add
		point val

		val_t = int
		opr_t(x) : assign x or add y

		(assign x)(assign y) = (assign x)
		(assign x)(add y) = (assign x)
		(add x)(assign y) = (assign y+x)
		(add x)(add y) = (add x+y)
		(assign or add)が閉じているので、この形をopr_tとして持てば良い.
		区間getがないとかなり考えやすいなあ
		というか、val_t同士の演算がいらなくて、opr_tだけでできてるなこれ

	*/
	struct val_t{
		ll x;
		val_t(){*this = e;}
		val_t(ll x):x(x){}

		const static val_t e;
		val_t operator+(const val_t &r) const {
			return val_t(x+r.x);
		}
		friend ostream& operator<<(ostream& o,const val_t& d){return o<<d.x;}
	};

	struct opr_t{
		bool is_add;
		ll x;
		opr_t(){*this = e;}
		opr_t(bool b,ll x):is_add(b),x(x){}

		const static opr_t e;
		friend ostream& operator<<(ostream& o,const opr_t& d){return o<<(d.is_add?"add":"assign")<<" "<<d.x;}
	};

	static opr_t getfg(const opr_t &f, const opr_t &g){
		if(f.is_add){
			if(g.is_add) return opr_t(true,f.x+g.x);
			else return opr_t(false,f.x+g.x);
		}else{
			return f;
		}
	}
	static void setg2fg(const opr_t &f, opr_t &g){	//g -> fg		f after g
		g = getfg(f,g);
	}
	static val_t act(const opr_t &f, const val_t &v,int k,int l,int r){	//assign f.x -> sum = 
		if(f.is_add) return val_t(v+f.x);
		else return val_t(f.x);
	}
};
const handler3::val_t handler3::val_t::e = val_t(0);
const handler3::opr_t handler3::opr_t::e = opr_t(true,0);	//単位元はadd 0

segtree_lazy<handler3> seg;

int N,L,t[100000],x[100000];

int pos(){
	int ub=L,lb=-1;
	while(ub-lb>1){
		int m=(ub+lb)/2;
		if(seg.getval(m)>=0) ub=m;
		else lb=m;
	}
	return ub;
}

int main(){
	cin>>N>>L;
	L++;
	seg.init(L);
	rep(i,N) cin>>t[i]>>x[i];
	long long sum=0;
	rep(i,N){
		sum+=x[i];
		seg.add(0,x[i],-1);
		seg.add(x[i],L,1);
		// show(seg.lazy);
		// cout<<"seg ";
		// rep(i,L) cout<<seg.getval(i)<<" ";
		// puts("");

		if(i==N||t[i]!=t[i+1]){
			int p=pos();
//			show(p);
			seg.assign(p,L,0);
			// cout<<"seg ";
			// rep(i,L) cout<<seg.getval(i)<<" ";
			// puts("");
		}
	}
	rep(i,L) sum+=seg.getval(i);
	cout<<sum<<endl;
}
 

Submission Info

Judge Result