QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#774847 | #9786. Magical Bags | ucup-team1004# | WA | 2ms | 12144kb | C++14 | 1.2kb | 2024-11-23 14:00:38 | 2024-11-23 14:00:39 |
Judging History
answer
#include<bits/stdc++.h>
#define mid ((l+r)>>1)
using namespace std;
const int N=2e5+10,M=N*30,MX=1e9;
int n,m,rt,ans,l[N],r[N],len;
vector<int> v[N];
pair<int,int> t[N];
set<int> t1,t2;
namespace seg
{
int t[M],ls[M],rs[M],cnt;
void modify(int l,int r,int &x,int w,int a)
{
if(!x) x=++cnt;
t[x]=max(t[x],a);
if(l==r) return;
if(w<=mid) modify(l,mid,ls[x],w,a);
else modify(mid+1,r,rs[x],w,a);
}
int query(int l,int r,int x,int w)
{
if(l>w||!x) return 0;
if(r<=w) return t[x];
return max(query(l,mid,ls[x],w),query(mid+1,r,rs[x],w));
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&m);
v[i].resize(m),ans+=min(m,2);
l[i]=MX,r[i]=0;
for(int j=0;j<m;j++)
scanf("%d",&v[i][j]),l[i]=min(l[i],v[i][j]),r[i]=max(r[i],v[i][j]);
t1.insert(l[i]),t2.insert(r[i]);
}
for(int i=1;i<=n;i++)
{
if((int)v[i].size()==1) continue;
int L=0,R=MX;
auto k=t2.upper_bound(l[i]);
if(k!=t2.end()) R=*k;
k=t1.lower_bound(r[i]);
if(k!=t1.begin()) L=*--k;
for(auto x:v[i])
if(L<x&&x<R) t[++len]={r[i],l[i]};
}
sort(t+1,t+len+1);
for(int i=1;i<=len;i++)
seg::modify(1,MX,rt,t[i].first,seg::query(1,MX,rt,t[i].second)+1);
printf("%d\n",ans-seg::t[1]);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 12084kb
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: 2ms
memory: 11928kb
input:
4 1 1 1 2 1 3 1 4
output:
4
result:
ok 1 number(s): "4"
Test #3:
score: 0
Accepted
time: 2ms
memory: 11960kb
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: 2ms
memory: 12144kb
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: 12104kb
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:
179
result:
wrong answer 1st numbers differ - expected: '177', found: '179'