QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#762485#8528. ChordsGrain_Depot08WA 2ms8540kbC++14658b2024-11-19 15:12:162024-11-19 15:12:17

Judging History

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

  • [2024-11-19 15:12:17]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:8540kb
  • [2024-11-19 15:12:16]
  • 提交

answer

#include<bits/stdc++.h>

using namespace std;

#define N 200005

int n,l[N];

vector<int>f[N];

int main(){
	int u,v;
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d%d",&u,&v);
		l[v]=u;
	}
	for(int i=1,j;i<=n+n;++i){
		f[i]=f[i-1];
		if(!l[i])continue;
		j=0;
		for(int k=0;k<f[i].size();++k){
			if(f[i][k]>l[i])j=k+1;
			else break;
		}
		if(f[i].size()==j){
			f[i].push_back(0);
		}else{
			f[i][j]=l[i];
		}
		for(int k=0;k<f[l[i]-1].size();++k){
			if(k+j+1==f[i].size()){
				f[i].push_back(0);
			}else{
				f[i][k+j+1]=max(f[i][k+j+1],f[l[i]-1][k]);
			}
		}
	}
	printf("%d",f[n+n].size());
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

5
1 2
4 10
7 9
3 5
6 8

output:

3

result:

ok 1 number(s): "3"

Test #2:

score: 0
Accepted
time: 2ms
memory: 8348kb

input:

1
1 2

output:

1

result:

ok 1 number(s): "1"

Test #3:

score: 0
Accepted
time: 2ms
memory: 8540kb

input:

2
1 3
2 4

output:

1

result:

ok 1 number(s): "1"

Test #4:

score: -100
Wrong Answer
time: 2ms
memory: 8464kb

input:

2
1 4
2 3

output:

1

result:

wrong answer 1st numbers differ - expected: '2', found: '1'