QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#358937#6553. Shared Memory SwitchKevin5307WA 38ms11384kbC++202.7kb2024-03-20 09:17:322024-03-20 09:17:32

Judging History

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

  • [2024-03-20 09:17:32]
  • 评测
  • 测评结果:WA
  • 用时:38ms
  • 内存:11384kb
  • [2024-03-20 09:17:32]
  • 提交

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]++;
	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));
				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]--;
					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: 100
Accepted
time: 1ms
memory: 5912kb

input:

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

output:

9
12 10 8 6 5 4 3 1 14 

result:

ok n=14

Test #2:

score: 0
Accepted
time: 1ms
memory: 5920kb

input:

14 4
1 1 1 2 2 2 -1 1 -1 1 -1 1 -1 1

output:

8
12 10 8 6 5 4 3 14 

result:

ok n=14

Test #3:

score: 0
Accepted
time: 0ms
memory: 3592kb

input:

0 0

output:

0

result:

ok n=0

Test #4:

score: 0
Accepted
time: 0ms
memory: 3588kb

input:

0 1

output:

0

result:

ok n=0

Test #5:

score: 0
Accepted
time: 1ms
memory: 5604kb

input:

3 0
1 -1 2

output:

0

result:

ok n=3

Test #6:

score: 0
Accepted
time: 17ms
memory: 7608kb

input:

200000 20
192797 145760 146491 109352 168621 58673 57243 7936 79733 3190 191130 169391 178004 120789 25556 56547 72241 59274 101245 129056 125785 138556 70154 63360 96036 73373 168059 46716 197905 106279 113884 190286 56438 128423 151368 193658 15613 17963 26833 136697 62679 188745 4515 151940 67745...

output:

40
44075 44074 44073 44072 44071 44070 44069 44068 44067 44066 44065 44064 44063 44062 44061 44060 44059 44058 44057 44056 44077 44078 44079 44080 44081 44082 44083 44084 44085 44086 44087 44088 44089 44090 44091 44092 44093 44094 44095 44096 

result:

ok n=200000

Test #7:

score: 0
Accepted
time: 38ms
memory: 10656kb

input:

200000 20
-1 -1 185081 -1 -1 34870 174269 47583 86208 69115 153529 101705 -1 -1 161748 11940 -1 -1 -1 191433 191546 -1 -1 108421 155301 -1 16678 -1 -1 -1 -1 179950 -1 169577 46923 -1 -1 -1 130194 -1 128371 -1 104684 -1 133162 170545 198827 -1 -1 72240 -1 -1 -1 110876 -1 -1 -1 80829 -1 84239 129224 -...

output:

100583
199999 199998 199991 199990 199988 199982 199980 199978 199977 199973 199971 199969 199967 199962 199959 199958 199957 199955 199953 199952 199950 199948 199946 199945 199942 199941 199940 199939 199938 199937 199935 199934 199933 199931 199930 199919 199918 199914 199909 199908 199906 199901...

result:

ok n=200000

Test #8:

score: -100
Wrong Answer
time: 35ms
memory: 11384kb

input:

200000 20
-1 -1 9380 -1 9380 9380 -1 9380 9380 9380 -1 9380 -1 9380 9380 9380 -1 -1 9380 9380 9380 -1 -1 -1 9380 -1 9380 -1 -1 -1 -1 -1 9380 -1 -1 -1 -1 -1 -1 9380 -1 9380 9380 -1 9380 9380 9380 -1 -1 -1 9380 9380 9380 -1 9380 9380 9380 9380 -1 9380 9380 9380 -1 9380 -1 -1 9380 -1 9380 -1 9380 9380 ...

output:

99676
199998 199997 199992 199989 199985 199983 199982 199979 199978 199975 199973 199969 199967 199965 199964 199959 199958 199957 199956 199953 199950 199949 199938 199937 199935 199934 199933 199932 199927 199920 199919 199915 199911 199910 199906 199900 199899 199898 199897 199896 199892 199890 ...

result:

wrong answer Buffer overflowed