QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#762485 | #8528. Chords | Grain_Depot08 | WA | 2ms | 8540kb | C++14 | 658b | 2024-11-19 15:12:16 | 2024-11-19 15:12:17 |
Judging History
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'