Submission #2074672

---

Source Code Expand

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

class RangeBIT {
	public:
	vector<long long> dat; int size_ = 1;
	
	void init(int size__){
		while(size_<=size__) size_*=2;
		dat.resize(size_*2, 0);
	}
	void add_(int l,int r,long long x,long long a,long long b,long long c){
		if(r<=a || b<=l) return;
		if(l<=a && b<=r){
			dat[c]+=x;return;
		}
		add_(l,r,x,a,(a+b)/2,c*2);
		add_(l,r,x,(a+b)/2,b,c*2+1);
	}
	void add(int l,int r,long long x){
		add_(l,r,x,0,size_,1);
	}
	long long Get(long long pos){
		pos+=size_;long long sum=0;
		while(pos>=1){
			sum+=dat[pos];pos/=2;
		}
		return sum;
	}
};

RangeBIT X; long long N,Q,t,p,ss; vector<long long>x[200009];

vector<tuple<long long,long long,long long>>solve(int pos){
	x[pos].push_back(0);x[pos].push_back(Q);
	sort(x[pos].begin(), x[pos].end());
	vector<tuple<long long,long long,long long>>A; long long sz = x[pos].size() - 2; sz *= -1;
	for(int i=0;i<x[pos].size()-1;i++){
		if(x[pos][i] != x[pos][i+1]) A.push_back(make_tuple(x[pos][i]+1, x[pos][i+1], sz));
		sz+=2;
	}
	return A;
}

void zero(int l,int r){
	while(l<r){
		long long V = X.Get(l);
		long long LL=l,RR=r,MM,maxn=r;
		for(int i=0;i<20;i++){
			MM=(LL+RR)/2;
			long long W = X.Get(MM);
			if(W!=V){maxn=min(maxn,MM);RR=MM;}
			else{LL=MM;}
		}
		X.add(l,maxn,-V);
		l=maxn;
	}
}

int main() {
	cin>>N>>Q;X.init(Q+2);
	for(int i=1;i<=N;i++){
		cin>>t>>p;ss+=p;
		x[t].push_back(p);
	}
	for(int i=1;i<=100000;i++){
		vector<tuple<long long,long long,long long>>L=solve(i);
		for(int j=0;j<L.size();j++){
			int l=get<0>(L[j]),r=get<1>(L[j]),p=get<2>(L[j]);
			X.add(l,r+1,p);
			long long J = X.Get(r);
			if(J>0){
				long long LL=0,RR=r+1,MM,maxn=r+1;
				for(int k=0;k<20;k++){
					MM=(LL+RR)/2;
					long long J2=X.Get(MM);
					if(J2>0){maxn=min(maxn,MM);RR=MM;}
					else{LL=MM;}
				}
				zero(maxn,r+1);
			}
		}
	}
	long long rr=ss;
	for(int i=1;i<=Q;i++){
		rr+=X.Get(i);
	}
	cout<<rr<<endl;
	return 0;
}

Submission Info

Judge Result