QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#861232#9982. Staircase Museumucup-team4717#WA 5ms12112kbC++14792b2025-01-18 16:35:312025-01-18 16:38:43

Judging History

This is the latest submission verdict.

  • [2025-01-18 16:38:43]
  • Judged
  • Verdict: WA
  • Time: 5ms
  • Memory: 12112kb
Show
  • [2025-01-18 16:35:31]
  • Submitted

answer

#include<bits/stdc++.h>
#define int long long
#define N 500005
using namespace std;
int T;
int n;
int L[N],R[N];
int l[N],r[N];
int f[N][2];
void sol(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++) scanf("%lld %lld",&L[i],&R[i]);
    int m=0;
    for(int i=1;i<=n;i++) if(L[i]!=L[i-1]||R[i]!=R[i-1]) m++,l[m]=L[i],r[m]=R[i];
    n=m;
    for(int i=1;i<=n;i++){
        f[i][0]=f[i-1][0];
        f[i][1]=f[i-1][1];
        if(l[i]!=l[i-1]) f[i][0]=f[i-1][0]+1;
        if(r[i]!=r[i-1]) f[i][1]=f[i-1][1]+1;
        if(i>=3&&r[i-2]<l[i]) f[i][0]=max(f[i][0],f[i-2][1]+2);
        if(i>=3&&r[i-2]>l[i]) f[i][1]=max(f[i][1],f[i-2][0]+2);
    }
    printf("%lld\n",max(f[n][0],f[n][1]));
}
signed main(){
    scanf("%lld",&T);
    while(T--) sol();
    return 0;
}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 1ms
memory: 12112kb

input:

1
1
1 1000000000

output:

1

result:

ok 1 number(s): "1"

Test #3:

score: -100
Wrong Answer
time: 5ms
memory: 12072kb

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
3
2
2
2
3
3
3
3
2
2
3
3
3
3
3
2
2
2
3
2
3
3
3
4
3
4
2
2
3
3
4
3
3
3
3
4
3
4
4
4
2
2
2
2
3
3
3
3
3
3
2
2
3
3
4
3
3
3
3
3
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
4
3
3
4
4
4
4
4
2
2
2
3
3
3
3
3
3
3
3
3
4
4
4
4
4
4
4
3
3
4
4
4
3
3
4
4
4
4
3
3
4
4
4
4
4
4
4
4
4
3
3
4
...

result:

wrong answer 13th numbers differ - expected: '3', found: '2'
English 繁體中文 简体中文

Server Time: 2025-02-08 19:13:51 | OpenSource Project