QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #460791 | #8528. Chords | ucup-team052# | WA | 1ms | 7628kb | C++14 | 1.5kb | 2024-07-02 09:44:59 | 2024-07-02 09:45:04 |
Judging History
answer
#include<bits/stdc++.h>
#ifdef xay5421
#define D(...) fprintf(stderr,__VA_ARGS__)
#define DD(...) D(#__VA_ARGS__ "="),debug_helper::debug(__VA_ARGS__),D("\n")
#include"/home/xay5421/debug.hpp"
#else
#define D(...) ((void)0)
#define DD(...) ((void)0)
#endif
#define pb push_back
#define eb emplace_back
#define SZ(x) ((int)(x).size())
#define each(x,v) for(auto&x:v)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
template<class T>void rd(T&x){int f=0,c;while(!isdigit(c=getchar()))f^=!(c^45);x=(c&15);while(isdigit(c=getchar()))x=x*10+(c&15);if(f)x=-x;}
template<class T>void pt(T x,int c=-1){if(x<0)putchar('-'),x=-x;if(x>9)pt(x/10);putchar(x%10+48);if(c!=-1)putchar(c);}
using namespace std;
using LL=long long;
using ULL=unsigned long long;
const int N=200005;
int n,a[N],b[N],go[N*2],suf[N*2];
int main(){
rd(n);
#ifndef xay5421
rep(i,1,n)rd(a[i]),rd(b[i]);
#else
static int id[N*2];
rep(i,1,n*2){
id[i]=i;
}
mt19937 rng(0);
shuffle(id+1,id+n*2+1,rng);
rep(i,1,n*2){
a[i]=id[i];
b[i]=id[i+n];
if(a[i]>b[i])swap(a[i],b[i]);
}
#endif
rep(i,1,n*4)go[i]=n*4+1;
rep(i,1,n){
go[a[i]]=b[i];
go[b[i]]=a[i]+n*2;
go[a[i]+n*2]=b[i]+n*2;
}
suf[n*4+1]=n*4+1;
per(i,n*4,1){
suf[i]=min(suf[i+1],go[i]);
}
int ans=0;
rep(_,1,n*2){
int cur=_;
int tt=0;
while(1){
if(suf[cur]<=_+n*2-1){
++tt;
cur=suf[cur]+1;
}else{
break;
}
}
ans=max(ans,tt);
}
pt(ans,'\n');
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5640kb
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: 7628kb
input:
1 1 2
output:
1
result:
ok 1 number(s): "1"
Test #3:
score: 0
Accepted
time: 1ms
memory: 5764kb
input:
2 1 3 2 4
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 1ms
memory: 5772kb
input:
2 1 4 2 3
output:
2
result:
ok 1 number(s): "2"
Test #5:
score: 0
Accepted
time: 0ms
memory: 5584kb
input:
3 3 5 1 4 2 6
output:
2
result:
ok 1 number(s): "2"
Test #6:
score: 0
Accepted
time: 1ms
memory: 5756kb
input:
4 2 7 1 6 3 8 4 5
output:
2
result:
ok 1 number(s): "2"
Test #7:
score: -100
Wrong Answer
time: 1ms
memory: 5724kb
input:
6 8 9 6 7 4 10 1 5 11 12 2 3
output:
4
result:
wrong answer 1st numbers differ - expected: '5', found: '4'