Submission #2074812

---

Source Code Expand

#include <bits/stdc++.h>
#define int long long
#define INF 1e+18
using namespace std;

int dat[100010];

void add(int i,int x){
	while(i < 100010){
		dat[i] += x;
		i += i & -i;
	}
}

int get(int i){
	int s = 0;
	while(i){
		s += dat[i];
		i -= i & -i;
	}
	return s;
}

signed main(){
	int n,l,t[100010],p[100010],ans = 0;
	vector<int> ts,evt[100010];
	cin >> n >> l;
	for(int i = 0;i < n;i++){
		cin >> t[i] >> p[i];
		ts.push_back(t[i]);
	}
	ts.erase(unique(ts.begin(),ts.end()),ts.end());
	for(int i = 0;i < n;i++){
		int ind = lower_bound(ts.begin(),ts.end(),t[i]) - ts.begin();
		evt[ind].push_back(p[i]);
	}
	for(int i = 0;i < ts.size();i++){
		add(1,-(int)evt[i].size());
		add(l + 1,evt[i].size());
		for(int v : evt[i]){
			ans += v;
			for(int j = 0;j < 2;j++){
				int low = -1,up = l;
				while(up - low > 1){
					int mid = (up + low) / 2;
					if(!get(mid + 1)) up = mid;
					else low = mid;
				}
				if(v + 1 < up + 1){
					add(v + 1,1);
					add(up + 1,-1);
				}
			}
		}
	}
	int sum = 0;
	for(int i = 0;i <= l;i++) sum += get(i + 1);
	cout << ans + sum << endl;
	return 0;
}

Submission Info

Judge Result