Submission #48273091

---

Source Code Expand

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

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;

#define rep(i,l,r) for(int i(l);i<=(r);++i)
#define per(i,r,l) for(int i(r);i>=(l);--i)
#define eb emplace_back
#define File(filename) freopen(filename ".in","r",stdin),freopen(filename ".out","w",stdout)

#ifdef EXODUS
	#define Debug(...) fprintf(stderr,__VA_ARGS__)
#else
	#define Debug(...) 0
#endif

//=========================================================================================================
// Something about IO

template<typename T>
void read(T &x){
	x=0;T flg=1;
	char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')flg=-1;ch=getchar();}
	while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	x*=flg;
}
template<typename T,typename... Args>
void read(T &x,Args &...args){read(x),read(args...);}

//=========================================================================================================
// Define the global variables here.

bool membg=0;

constexpr int N=2e5+7,V=1e9;
int n;
int f[N];

struct Sgt{
#define ls(k) t[k].ls
#define rs(k) t[k].rs
	struct node{int ls,rs;int mxv;}t[N<<6];
	int tot;
	void modify(int l,int r,int &k,int p,int v){
		if(!k)k=++tot,t[k].mxv=-1e9;
		t[k].mxv=max(t[k].mxv,v);
		if(l==r)return;
		int mid=(l+r)>>1;
		if(p<=mid)modify(l,mid,ls(k),p,v);
		else modify(mid+1,r,rs(k),p,v);
	}
	int query(int l,int r,int k,int ql,int qr){
		if(ql>qr||!k)return -1e9;
		if(ql<=l&&r<=qr)return t[k].mxv;
		int mid=(l+r)>>1;int res=-1e9;
		if(ql<=mid)res=max(res,query(l,mid,ls(k),ql,qr));
		if(mid<qr)res=max(res,query(mid+1,r,rs(k),ql,qr));
		return res;
	}
#undef ls
#undef rs
}sgt[2];
int rt[2];
int l[N],r[N];

bool memed=0;

//=========================================================================================================
// Code here.

void solve(){
	read(n);
	for(int i=1;i<=n;i++)read(l[i],r[i]);
	for(int i=1;i<=n;i++){
		f[i]=max(0,sgt[0].query(1,V,rt[0],1,l[i]-1))+r[i]-l[i]+1;
		f[i]=max(f[i],sgt[1].query(1,V,rt[1],l[i],r[i])+r[i]);
		// printf("%d\n",f[i]);
		sgt[0].modify(1,V,rt[0],r[i],f[i]);
		sgt[1].modify(1,V,rt[1],r[i],f[i]-r[i]);
	}
	printf("%d\n",*max_element(f+1,f+n+1));
	return;
}


//=========================================================================================================

int main(){
	Debug("%.3lfMB\n",fabs(&memed-&membg)/1024.0/1024.0);
	int timbg=clock();
	int T=1;
	while(T--)solve();
	int timed=clock();
	Debug("%.3lfs\n",1.0*(timed-timbg)/CLOCKS_PER_SEC);
	fflush(stdout);
	return 0;
}

Submission Info

Compile Error

Main.cpp: In function ‘int main()’:
Main.cpp:18:28: warning: statement has no effect [-Wunused-value]
   18 |         #define Debug(...) 0
      |                            ^
Main.cpp:94:9: note: in expansion of macro ‘Debug’
   94 |         Debug("%.3lfMB\n",fabs(&memed-&membg)/1024.0/1024.0);
      |         ^~~~~
Main.cpp:18:28: warning: statement has no effect [-Wunused-value]
   18 |         #define Debug(...) 0
      |                            ^
Main.cpp:99:9: note: in expansion of macro ‘Debug’
   99 |         Debug("%.3lfs\n",1.0*(timed-timbg)/CLOCKS_PER_SEC);
      |         ^~~~~
Main.cpp:95:13: warning: unused variable ‘timbg’ [-Wunused-variable]
   95 |         int timbg=clock();
      |             ^~~~~
Main.cpp:98:13: warning: unused variable ‘timed’ [-Wunused-variable]
   98 |         int timed=clock();
      |             ^~~~~

Judge Result