QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#774017 | #9786. Magical Bags | ucup-team3510# | WA | 1ms | 5936kb | C++20 | 1.6kb | 2024-11-23 11:17:53 | 2024-11-23 11:17:55 |
Judging History
answer
#include<iostream>
#include<vector>
#include<set>
#include<algorithm>
using namespace std;
int n,ans=0,l[200010],r[200010],A[200010];
vector<int> a[200010],v;
inline bool cmp(const vector<int> &x,
const vector<int> &y)
{
return x.back()<y.back();
}
int f[200010];
inline void add(int x,int y)
{
for(;x<=n;f[x]=max(f[x],y),x+=x&-x);
}
inline int query(int x)
{
int ret=0;
for(;x;ret=max(ret,f[x]),x&=x-1);
return ret;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
for(int i=1,x;i<=n;i++)
{
cin>>x;
a[i].resize(x);
for(int j=0;j<x;j++)
{
cin>>a[i][j];
v.emplace_back(a[i][j]);
}
sort(a[i].begin(),a[i].end());
ans+=min(2,x);
}
sort(v.begin(),v.end());
int num=unique(v.begin(),v.end())-v.begin();
for(int i=1;i<=n;i++)
{
for(int j=0;j<a[i].size();j++)
{
a[i][j]=lower_bound(v.begin(),
v.begin()+num,a[i][j])-v.begin()+1;
}
}
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;i++)
{
int L=a[i][0];
int R=A[i]=a[i].back();
add(num-R+1,L);
if(a[i].size()==1)
{
continue;
}
l[i]=query(num-L);
r[i]=A[lower_bound(A+1,A+i+1,L)-A];
}
set<int> s;
for(int i=n;i;i--)
{
if(a[i].size()==1)
{
continue;
}
s.insert(-a[i][0]);
auto it=s.lower_bound(-a[i].back());
l[i]=max(l[i],-(*it));
}
for(int i=1,last=0;i<=n;i++)
{
if(a[i].size()==1||l[i]>r[i])
{
continue;
}
if(last<a[i][0])
{
int p=lower_bound(a[i].begin(),
a[i].end(),l[i])-a[i].begin();
if(p==a[i].size()||a[i][p]>r[i])
{
continue;
}
last=a[i].back();
ans--;
}
}
cout<<ans<<endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5656kb
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: 1ms
memory: 5668kb
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: 5908kb
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: 5936kb
input:
4 1 1 1 2 1 3 1 4
output:
4
result:
ok 1 number(s): "4"
Test #5:
score: 0
Accepted
time: 1ms
memory: 5896kb
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: -100
Wrong Answer
time: 1ms
memory: 5932kb
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:
173
result:
wrong answer 1st numbers differ - expected: '175', found: '173'