QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#774305 | #9786. Magical Bags | ucup-team4454# | WA | 3ms | 36380kb | C++14 | 3.9kb | 2024-11-23 12:55:13 | 2024-11-23 12:55:14 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int ret=0,flg=0;
char c=getchar();
while(c<'0'||c>'9')flg|=c=='-',c=getchar();
while(c>='0'&&c<='9')ret=(ret<<3)+(ret<<1)+c-'0',c=getchar();
return flg?-ret:ret;
}
inline void write(int x,bool flg){
char a[21];
if(!x)putchar('0');
if(x<0)putchar('-'),x=-x;
int cnt=0;
while(x){
a[++cnt]=x%10+'0';
x/=10;
}
while(cnt)putchar(a[cnt--]);
putchar(flg?'\n':' ');
return ;
}
#define maxn 400010
int n,a[maxn],b[maxn],A[maxn],B[maxn];
int l[maxn],r[maxn];
vector<int> v[maxn];
int la[maxn<<2],ra[maxn<<2],lb[maxn<<2],rb[maxn<<2];
void build(int L,int R,int p){
//cout<<L<<" "<<R<<endl;
if(L==R){
la[p]=l[a[L]];
ra[p]=r[a[L]];
lb[p]=l[b[L]];
rb[p]=r[b[L]];
return ;
}
int mid(L+R>>1);
build(L,mid,p<<1);
build(mid+1,R,p<<1|1);
la[p]=max(la[p<<1],la[p<<1|1]);
ra[p]=min(ra[p<<1],ra[p<<1|1]);
lb[p]=max(lb[p<<1],lb[p<<1|1]);
rb[p]=min(rb[p<<1],rb[p<<1|1]);
return ;
}
void query1(int l_,int r_,int L,int R,int &La,int &Ra,int p){
if(L<=l_&&r_<=R){
La=max(La,la[p]);
Ra=min(Ra,ra[p]);
return ;
}
int mid(l_+r_>>1);
if(L<=mid)return query1(l_,mid,L,R,La,Ra,p<<1);
if(R>mid)return query1(mid+1,r_,L,R,La,Ra,p<<1|1);
return ;
}
void query2(int l_,int r_,int L,int R,int &Lb,int &Rb,int p){
if(L<=l_&&r_<=R){
Lb=max(Lb,lb[p]);
Rb=min(Rb,rb[p]);
return ;
}
int mid(l_+r_>>1);
if(L<=mid)return query2(l_,mid,L,R,Lb,Rb,p<<1);
if(R>mid)return query2(mid+1,r_,L,R,Lb,Rb,p<<1|1);
return ;
}
void modify1(int l_,int r_,int x,int p){
if(l_==r_){
la[p]=l[a[l_]];
ra[p]=r[a[l_]];
return ;
}
int mid(l_+r_>>1);
if(x<=mid)modify1(l_,mid,x,p<<1);
else modify1(mid+1,r_,x,p<<1|1);
la[p]=max(la[p<<1],la[p<<1|1]);
ra[p]=min(ra[p<<1],ra[p<<1|1]);
return ;
}
void modify2(int l_,int r_,int x,int p){
if(l_==r_){
lb[p]=l[b[l_]];
rb[p]=r[b[l_]];
return ;
}
int mid(l_+r_>>1);
if(x<=mid)modify2(l_,mid,x,p<<1);
else modify2(mid+1,r_,x,p<<1|1);
lb[p]=max(lb[p<<1],lb[p<<1|1]);
rb[p]=min(rb[p<<1],rb[p<<1|1]);
return ;
}
int id1[maxn],id2[maxn],fl[maxn],id[maxn];
int main(){
n=read();
int ans=0;
for(int i=1;i<=n;i++){
int k=read();
l[i]=1e9,r[i]=0;
for(int j=1;j<=k;j++){
int x=read();
l[i]=min(l[i],x);
r[i]=max(r[i],x);
v[i].push_back(x);
}
ans+=2-(k==1);
a[i]=b[i]=id[i]=i;
}
sort(a+1,a+n+1,[](int x,int y){
return r[x]<r[y];
});
sort(b+1,b+n+1,[](int x,int y){
return l[x]<l[y];
});
sort(id+1,id+n+1,[](int x,int y){
return r[x]-l[x]<r[y]-l[y];
});
//cout<<"ee"<<endl;
build(1,n,1);
// cout<<ans<<endl;
for(int i=1,mx=0;i<=n;i++){
if(l[a[i]]<mx){
fl[a[i]]=1;
}
mx=max(mx,l[a[i]]);
}
for(int i=1;i<=n;i++){
A[i]=r[a[i]];
B[i]=l[b[i]];
id1[a[i]]=i;
id2[b[i]]=i;
}
for(int j=1,i;j<=n;j++){
i=id[j];//cout<<i<<endl;
if(l[i]==r[i])continue;
int L=l[i],R=r[i];
int pos=lower_bound(A+1,A+n+1,l[i])-A;
query1(1,n,pos,id1[i],L,R,1);
pos=lower_bound(B+1,B+n+1,r[i])-B-1;
query2(1,n,id2[i],pos,L,R,1);
// cout<<i<<" "<<L<<" "<<R<<endl;
for(auto t:v[i]){
if(L<=t&&t<=R){
ans--;
l[i]=r[i]=t;
modify1(1,n,id1[i],1);
modify2(1,n,id2[i],1);
break;
}
}
}write(ans,1);
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 36380kb
input:
4 3 4 7 10 2 1 9 4 11 2 8 14 3 6 12 13
output:
7
result:
ok 1 number(s): "7"
Test #2:
score: 0
Accepted
time: 0ms
memory: 34416kb
input:
4 1 1 1 2 1 3 1 4
output:
4
result:
ok 1 number(s): "4"
Test #3:
score: 0
Accepted
time: 3ms
memory: 34256kb
input:
4 3 4 7 10 2 1 9 4 11 2 8 14 3 6 12 13
output:
7
result:
ok 1 number(s): "7"
Test #4:
score: 0
Accepted
time: 0ms
memory: 34220kb
input:
4 1 1 1 2 1 3 1 4
output:
4
result:
ok 1 number(s): "4"
Test #5:
score: -100
Wrong Answer
time: 0ms
memory: 34268kb
input:
100 4 372861091 407948190 424244630 359746969 6 568180757 527358812 494745349 665803213 674832670 586694351 4 696340797 775899164 919971335 716827187 4 123145962 344250363 122030550 251739234 4 342654413 368648894 150539766 255189030 1 194505887 3 755984448 736803561 745474041 4 709314938 498953418 ...
output:
160
result:
wrong answer 1st numbers differ - expected: '177', found: '160'