QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#774104 | #9786. Magical Bags | ucup-team4454# | WA | 0ms | 34428kb | C++14 | 3.7kb | 2024-11-23 11:49:01 | 2024-11-23 11:49:02 |
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];
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-(l[i]==r[i]);
a[i]=b[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];
});
//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 i=1;i<=n;i++){
if(l[i]==r[i]||fl[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;
query2(1,n,pos,id2[i],L,R,1);
// cout<<i<<" "<<L<<" "<<R<<endl;
for(auto t:v[i]){
if(t>=L&&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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 32324kb
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: 32396kb
input:
4 1 1 1 2 1 3 1 4
output:
4
result:
ok 1 number(s): "4"
Test #3:
score: 0
Accepted
time: 0ms
memory: 32264kb
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: 34428kb
input:
4 1 1 1 2 1 3 1 4
output:
4
result:
ok 1 number(s): "4"
Test #5:
score: 0
Accepted
time: 0ms
memory: 32404kb
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:
177
result:
ok 1 number(s): "177"
Test #6:
score: 0
Accepted
time: 0ms
memory: 32380kb
input:
100 5 128474911 128789041 128389100 128571722 128449204 4 190783009 179144907 191954599 169739385 7 922968028 923017780 923012667 922993373 923012653 923010830 922983606 1 399117777 8 693609160 693615962 692956804 692902832 694104582 693605539 693750551 692909362 4 133590022 156691169 120354087 1477...
output:
175
result:
ok 1 number(s): "175"
Test #7:
score: 0
Accepted
time: 0ms
memory: 32320kb
input:
100 3 667874577 779650612 311873157 4 315088665 510831928 558038267 371108692 9 755153639 761562353 770756971 766146687 755341778 756786965 752029435 762376276 769269467 6 104846116 127832365 303763622 308914288 193368850 212600340 4 278400790 520739777 691975492 363532266 3 882063076 834874749 8790...
output:
188
result:
ok 1 number(s): "188"
Test #8:
score: 0
Accepted
time: 0ms
memory: 32316kb
input:
100 3 906356952 850278493 852337285 4 171262913 167082071 210705401 185031512 7 802495630 790288362 821278829 774987331 774050880 798490416 758938148 5 15709100 243583562 406822217 439043410 105298894 3 615900896 610909553 657678763 4 829696557 810959924 841612668 819869747 6 853997379 864469575 881...
output:
180
result:
ok 1 number(s): "180"
Test #9:
score: 0
Accepted
time: 0ms
memory: 32308kb
input:
100 4 364081200 540650381 353768306 122255830 7 936882622 937778158 941372288 943745873 947703805 938067346 944019473 7 598655091 679073706 723959930 579018281 860392698 852744534 665808681 1 557290205 3 838323287 764154463 864559801 4 952241609 888202173 792726290 886689636 6 653946054 841409940 83...
output:
175
result:
ok 1 number(s): "175"
Test #10:
score: -100
Wrong Answer
time: 0ms
memory: 32276kb
input:
100 1 440195292 6 859787120 847131414 854112709 869067609 839981608 845676179 5 206450888 209708811 207370111 201853766 207539046 1 555976272 1 938758019 1 413646308 9 252799098 254947888 265345550 249752370 261338550 251583211 248642444 266900460 261558897 5 83936282 116530372 99708225 112074514 96...
output:
150
result:
wrong answer 1st numbers differ - expected: '151', found: '150'