QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#358938#6553. Shared Memory SwitchKevin5307ML 0ms0kbC++202.7kb2024-03-20 09:19:052024-03-20 09:19:06

Judging History

你现在查看的是最新测评结果

  • [2024-03-20 09:19:06]
  • 评测
  • 测评结果:ML
  • 用时:0ms
  • 内存:0kb
  • [2024-03-20 09:19:05]
  • 提交

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;
}

详细

Test #1:

score: 0
Memory Limit Exceeded

input:

14 5
1 1 1 2 2 2 -1 1 -1 1 -1 1 -1 1

output:


result: