QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#762164 | #8528. Chords | Grain_Depot08 | WA | 1ms | 6392kb | C++14 | 699b | 2024-11-19 14:00:51 | 2024-11-19 14:00:55 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define N 100005
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;
}
f[0].push_back(0);
for(int i=1,j;i<=n+n;++i){
f[i]=f[i-1];
f[i][0]=i;
if(!l[i])continue;
for(j=f[i].size()-1;~j;--j){
if(f[i-1][j]>l[i]){
break;
}
}
if(f[i].size()==j+1){
f[i].push_back(l[i]);
}else{
f[i][j+1]=l[i];
}
for(int k=1;k<f[l[i]-1].size();++k){
if(k+j+1==f[i].size()){
f[i].push_back(f[l[i]-1][k]);
}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: 1ms
memory: 6392kb
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: 1ms
memory: 6256kb
input:
1 1 2
output:
1
result:
ok 1 number(s): "1"
Test #3:
score: -100
Wrong Answer
time: 1ms
memory: 6388kb
input:
2 1 3 2 4
output:
2
result:
wrong answer 1st numbers differ - expected: '1', found: '2'