Submission #618385

---

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;
typedef long long ll;
int N,L,t[100000],x[100000];
ll inf=1e18;
struct segtree{
	static const int p2=1<<17;
	int val[p2*2]={};
	ll at(int x){
		ll ret=0;
		x+=p2;
		while(x){
			ret+=val[x];
			x/=2;
		}
		return ret;
	}
	void add(int a,int b,int l,int r,int k,int v){
		if(b<=l||r<=a) return;
		if(a<=l&&r<=b){
			val[k]+=v;
			return;
		}
		add(a,b,l,(l+r)/2,k*2,v);
		add(a,b,(l+r)/2,r,k*2+1,v);
	}
	void add(int a,int b,int v){
		add(a,b,0,p2,1,v);
	}
	int pos(){
		int ub=L+1,lb=-1;
		while(ub-lb>1){
			int m=(ub+lb)/2;
			if(at(m)>=0) ub=m;
			else lb=m;
		}
		return ub;
	}
} seg;
int main(){
	cin>>N>>L;
	rep(i,N) cin>>t[i]>>x[i];
	int le=0;
	rep1(i,N){
		if(i==N||t[i-1]!=t[i]){
			reverse(x+le,x+i);
			le=i;
		}
	}
	ll sum=0;
	rep(i,N){
		sum+=x[i];
		int p=seg.pos();
		seg.add(0,x[i],-1);
		seg.add(x[i],p,1);
//		show(x[i]);
//		show(p);
	}
	rep(i,L+1) sum+=seg.at(i);
	cout<<sum<<endl;
}

Submission Info

Judge Result