Submission #1792444

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 1000000007
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
struct segtree{
	#define s (1<<18)
	int seg[s];
	void init(){
		fill(seg,seg+s,-1e9);
	}
	void update(int k,int a){
		k+=s/2-1; seg[k]=max(seg[k],a);
		while(k>0){
			k=(k-1)/2;
			seg[k]=max(seg[k*2+1],seg[k*2+2]);
		}
	}
	int query(int a,int b,int k,int l,int r){
		if(r<a || b<l || b<a) return -1e9;
		if(a<=l && r<=b) return seg[k];
		else{
			int vl=query(a,b,k*2+1,l,(l+r)/2);
			int vr=query(a,b,k*2+2,(l+r)/2+1,r);
			return max(vl,vr);
		}
	}
}seg1,seg2;
int n,m; P p[100005];
int main(){
	cin>>n>>m;
	rep(i,n){
		int a,b;
		cin>>a>>b; a++;
		p[i] = mp(a,b);
	}
	seg1.init(); seg2.init();
	sort(p,p+n);
	seg1.update(0,0);
	seg2.update(0,0);
	int ans = 0;
	for(int i=0;i<n;i++){
		int L = p[i].fi,R = L-1+p[i].sc,dp = -1e9;
		int v = seg1.query(0,L-1,0,0,(1<<17)-1);
		dp = max(dp,v+p[i].sc);
		int v2 = seg2.query(L,R-1,0,0,(1<<17)-1);
		dp = max(dp,v2+R+L-1);
		ans = max(ans,dp);
		seg1.update(R,dp);
		seg2.update(R,dp-2*R);
	}
	cout<<ans<<endl;
}

Submission Info

Judge Result