线段树,WA#7,求hack
查看原帖
线段树,WA#7,求hack
220285
Saber_Master楼主2022/9/12 11:54
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<map>
#include<queue>
#include<vector>
#include<set>
#include<bitset>
#include<cassert>
#include<ctime>
#define next MabLcdG
#define R register
#define debug puts("lg")
#define mod 1000000007
#define chkmax(x, y) (x=max(x, y))
#define chkmin(x, y) (x=min(x, y))
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef double dl;
template<typename T> void read(T &x);
template<typename T> void write(T x);
template<typename T> void writesp(T x);
template<typename T> void writeln(T x);

const ll N=1e6+5;

ll n;
struct node {
	ll l, r;
}cow[N];
ll rem[N<<1], tot;
ll f[N<<1];
ll dat[N<<3];
inline void update(ll p, ll l, ll r, ll u, ll x) {
	if (l==r) return (void) (chkmax(dat[p], x));
	ll mid=l+r>>1;
	if (u<=mid) update(p<<1, l, mid, u, x);
	else update(p<<1|1, mid+1, r, u, x);
	dat[p]=max(dat[p<<1], dat[p<<1|1]);
}
inline ll query(ll p, ll l, ll r, ll u, ll v) {
	if (u<=l && r<=v) return dat[p];
	ll mid=l+r>>1, x=0;
	if (u<=mid) chkmax(x, query(p<<1, l, mid, u, v));
	if (v>mid) chkmax(x, query(p<<1|1, mid+1, r, u, v));
	return x;
}

inline bool cmp(node a, node b) {
	return (a.r==b.r)?(a.l<b.l):(a.r<b.r);
}
/*
3
1 2
7 8
3 4

*/
int main(){
	read(n);
	for (R ll i=1; i<=n; i++) {
		read(cow[i].l); read(cow[i].r);
		rem[++tot]=cow[i].l; rem[++tot]=cow[i].r;
	}
	sort(rem+1, rem+tot+1);
	tot=unique(rem+1, rem+tot+1)-rem;
	for (R ll i=1; i<=n; i++) {
		cow[i].l=lower_bound(rem+1, rem+tot+1, cow[i].l)-rem;
		cow[i].r=lower_bound(rem+1, rem+tot+1, cow[i].r)-rem;
	}
	sort(cow+1, cow+n+1, cmp);
	for (R ll i=1; i<=n; i++) {
		if (cow[i].l==1) chkmax(f[cow[i].r], rem[cow[i].r]-rem[cow[i].l]+1);
		else chkmax(f[cow[i].r], rem[cow[i].r]-rem[cow[i].l]+1+query(1, 1, tot, 1, cow[i].l-1));
		update(1, 1, tot, cow[i].r, f[cow[i].r]);
	}
	writeln(query(1, 1, tot, 1, tot));
}
template<typename T> void read(T &x){
	x=0; int t=1;
	char wn=getchar();
	while (wn<'0' || wn>'9'){
		if (wn=='-') t=-1;
		wn=getchar();
	}
	while (wn>='0' && wn<='9'){
		x=x*10+wn-'0'; wn=getchar();
	}
	x*=t;
}
template<typename T> void write(T x){
	if (x<0){putchar('-'); x=-x;}
	if (x<=9){putchar(x+'0'); return;}
	write(x/10); putchar(x%10+'0');
}
template<typename T> void writesp(T x){
	write(x); putchar(' ');
}

template<typename T> void writeln(T x){
	write(x); putchar('\n');
}
2022/9/12 11:54
加载中...