Submission #881996

---

Source Code Expand

#include <bits/stdc++.h>

#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)

#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=int(a)-1;i>=int(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)

#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define popcount(n) (__builtin_popcountll(n))

using namespace std;

template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;}
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;}

using ll=long long;
using R=long double;
const R EPS=1e-9; // [-1000,1000]->EPS=1e-8 [-10000,10000]->EPS=1e-7
inline int sgn(const R& r){return(r > EPS)-(r < -EPS);}
inline R sq(R x){return sqrt(max<R>(x,0.0));}

const int dx[8]={1,0,-1,0,1,-1,-1,1};
const int dy[8]={0,1,0,-1,1,1,-1,-1};

// Problem Specific Parameter:


const int m=1<<17;
ll val[2*m];

void update(int l, int r, int x) {
 	for (l += m, r += m; l < r; l >>= 1, r >>= 1) {
		if(l&1) val[l++]+= x;
		if(r&1) val[--r]+= x;
  	}
}

int at(int p) {
 	int ret = 0;
 	for(p += m; p > 0; p >>= 1) ret += val[p];
	return ret;
}

int find_positive(int len){
	int l=-1,r=len+1;
	while(r-l>1){
		const int mid=(l+r)/2;
		if(at(mid)<=0)
			l=mid;
		else
			r=mid;
	}
	return r;
}


ll p[100010],t[100010];

int main(void){
	int n,l;
	cin >> n >> l;
	rep(i,n) cin >> t[i] >> p[i];

	rep(i,n){
		int to=i;
		while(to<n && t[i]==t[to]) to++;
		reverse(p+i,p+to);
		reverse(t+i,t+to);
		i=to-1;
	}

	ll ans=0LL;
	rep(i,n){
		ans+=p[i];
		
		update(0,p[i],-1);
		update(p[i],l+1,+1);

		int pos=find_positive(l);
		update(pos,l+1,-1);
	}

	rep(i,l) ans+=at(i);
	cout << ans << endl;
	return 0;
}

Submission Info

Judge Result