QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#865201#9982. Staircase MuseumyhdddWA 3ms11980kbC++201.6kb2025-01-21 16:00:532025-01-21 16:00:55

Judging History

你现在查看的是最新测评结果

  • [2025-01-21 16:00:55]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:11980kb
  • [2025-01-21 16:00:53]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
#define mod 998244353ll
#define pii pair<int,int>
#define fi first
#define se second
#define mems(x,y) memset(x,y,sizeof(x))
#define pb push_back
#define db double
using namespace std;
const int maxn=200010;
const int inf=1e18;
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch-48);ch=getchar();}
	return x*f;
}
bool Mbe;

int n,l[maxn],r[maxn],m;
pii a[maxn];
int lsh[maxn],len;
#define lb(x) (x&(-x))
int tree[maxn];
void upd(int x,int w){
	while(x<=len)tree[x]=max(tree[x],w),x+=lb(x);
}
int que(int x){
	int res=0;
	while(x)res=max(res,tree[x]),x-=lb(x);
	return res;
}
void work(){
	n=read();int ans=0;
	a[m=1]={0,2};
	for(int i=1;i<=n;i++){
		l[i]=read()*2,r[i]=read()*2;
	}
	for(int i=1;i<=n;i++){
		if(r[i+1]>r[i])a[++m]={2*i,r[i]+1};
		if(i!=m)a[++m]={2*i+1,l[i]};
	}
	sort(a+1,a+m+1);
	// for(int i=1;i<=m;i++)cout<<a[i].fi<<" "<<a[i].se<<"\n";
	len=0;for(int i=1;i<=m;i++)lsh[++len]=a[i].se;
	sort(lsh+1,lsh+len+1),len=unique(lsh+1,lsh+len+1)-lsh-1;
	for(int i=1;i<=m;i++)a[i].se=lower_bound(lsh+1,lsh+len+1,a[i].se)-lsh;
	for(int i=1;i<=len;i++)tree[i]=0;
	for(int i=1;i<=m;i++){
		int dp=que(a[i].se-1)+1;
		upd(a[i].se,dp);
		ans=max(ans,dp);
	}
	printf("%lld\n",ans);
}

// \
444

bool Med;
int T;
signed main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	
//	ios::sync_with_stdio(0);
//	cin.tie(0);cout.tie(0);
	
//	cerr<<(&Mbe-&Med)/1048576.0<<" MB\n";
	
	T=read();
	while(T--)work();
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 11956kb

input:

4
3
1 2
1 3
1 3
3
1 2
2 3
3 3
3
1 1
1 3
3 3
4
1 2
2 3
3 4
4 5

output:

2
3
3
4

result:

ok 4 number(s): "2 3 3 4"

Test #2:

score: 0
Accepted
time: 0ms
memory: 8008kb

input:

1
1
1 1000000000

output:

1

result:

ok 1 number(s): "1"

Test #3:

score: -100
Wrong Answer
time: 3ms
memory: 11980kb

input:

9653
1
1 1
2
1 1
1 1
3
1 1
1 1
1 1
4
1 1
1 1
1 1
1 1
5
1 1
1 1
1 1
1 1
1 1
6
1 1
1 1
1 1
1 1
1 1
1 1
6
1 2
1 2
1 2
1 2
1 2
2 2
6
1 1
1 1
1 1
1 1
1 1
1 2
6
1 2
1 2
1 2
1 2
1 2
2 3
5
1 2
1 2
1 2
1 2
2 2
6
1 2
1 2
1 2
1 2
2 2
2 2
6
1 3
1 3
1 3
1 3
2 3
3 3
6
1 2
1 2
1 2
1 2
2 2
2 3
6
1 3
1 3
1 3
1 3
2 3...

output:

1
1
1
1
1
1
2
2
2
2
2
3
2
2
3
2
2
3
3
3
3
2
2
3
3
3
3
3
2
3
2
3
3
3
3
3
4
3
3
3
2
3
3
3
3
3
2
2
3
3
3
3
3
3
3
2
2
3
3
3
3
3
3
3
2
3
3
3
3
3
3
3
4
3
3
4
4
3
3
4
4
4
4
3
3
3
4
4
3
3
4
4
4
4
3
3
4
3
3
4
3
4
4
4
4
4
2
3
2
3
3
3
3
3
3
3
3
3
4
3
3
4
4
3
3
4
3
3
4
4
3
3
4
4
4
4
3
3
3
4
4
3
3
4
4
4
4
3
3
4
...

result:

wrong answer 13th numbers differ - expected: '3', found: '2'