QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#358938 | #6553. Shared Memory Switch | Kevin5307 | ML | 0ms | 0kb | C++20 | 2.7kb | 2024-03-20 09:19:05 | 2024-03-20 09:19:06 |
answer
//Author: Kevin
#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
#define ll long long
#define ull unsigned ll
#define pb emplace_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
#define srt(x) sort(ALL(x))
#define rev(x) reverse(ALL(x))
#define rsrt(x) sort(rALL(x))
#define sz(x) (int)(x.size())
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
#define longer __int128_t
void die(string S){puts(S.c_str());exit(0);}
int used[200200];
int q[200200];
bool flag[200200];
int delta[200200];
vector<int> pool;
int mx[200200<<2],tag[200200<<2];
#define ls (x<<1)
#define rs (ls|1)
void update(int x,int l,int r,int ql,int qr,int v)
{
if(ql<=l&&r<=qr)
{
tag[x]+=v;
mx[x]+=v;
return ;
}
int mid=(l+r)/2;
if(ql<=mid)
update(ls,l,mid,ql,qr,v);
if(qr>mid)
update(rs,mid+1,r,ql,qr,v);
mx[x]=max(mx[ls],mx[rs])+tag[x];
}
int query(int x,int l,int r,int ql,int qr)
{
if(l==ql&&r==qr)
return mx[x];
int mid=(l+r)/2;
if(qr<=mid)
return query(ls,l,mid,ql,qr)+tag[x];
if(ql>mid)
return query(rs,mid+1,r,ql,qr)+tag[x];
return max(query(ls,l,mid,ql,mid),query(rs,mid+1,r,mid+1,qr))+tag[x];
}
#undef ls
#undef rs
int rt[200200],tot;
int ls[200200<<5],rs[200200<<5],cnt[200200<<5];
int ins(int x,int l,int r,int p)
{
if(!x) x=++tot;
cnt[x]++;
if(l==r) return x;
int mid=(l+r)/2;
if(p<=mid)
ls[x]=ins(ls[x],l,mid,p);
else
rs[x]=ins(rs[x],mid+1,r,p);
}
int findr(int x,int l,int r,int lim)
{
if(!x) return min(r,lim);
if(l==r) return l;
int mid=(l+r)/2;
int rc=max(0,min(r,lim)-mid);
if(rc==cnt[rs[x]])
return findr(ls[x],l,mid,lim);
else
return findr(rs[x],mid+1,r,lim);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n,b;
cin>>n>>b;
for(int i=1;i<=n;i++)
cin>>q[i];
int s=0;
vector<int> vec;
for(int i=n;i>=1;i--)
if(q[i]==-1)
{
s++;
pool.pb(i);
}
else
{
if(used[q[i]]<s)
{
int pos=findr(rt[q[i]],1,n,sz(pool));
int tmp=pos;
pos=pool[pos-1];
if(query(1,1,n,i,pos-1)>=b)
flag[i]=1;
else
{
vec.pb(i);
used[q[i]]++;
delta[i]++;
delta[pos]--;
rt[q[i]]=ins(rt[q[i]],1,n,tmp);
update(1,1,n,i,pos-1,1);
}
}
else
flag[i]=1;
}
vector<int> vec2;
for(int i=1;i<=n;i++)
{
delta[i]+=delta[i-1];
if(flag[i])
vec2.pb(i);
while(sz(vec2)>b-delta[i])
vec2.pop_back();
}
for(auto x:vec2)
vec.pb(x);
cout<<sz(vec)<<'\n';
for(auto x:vec)
cout<<x<<" ";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Memory Limit Exceeded
input:
14 5 1 1 1 2 2 2 -1 1 -1 1 -1 1 -1 1