QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#358948#6553. Shared Memory SwitchKevin5307WA 86ms51104kbC++202.8kb2024-03-20 09:42:302024-03-20 09:42:30

Judging History

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

  • [2024-03-20 09:42:30]
  • 评测
  • 测评结果:WA
  • 用时:86ms
  • 内存:51104kb
  • [2024-03-20 09:42:30]
  • 提交

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);
	return x;
}
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;
	vector<pii> seg;
	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));
				seg.pb(i,pool[pos-1]);
				rt[q[i]]=ins(rt[q[i]],1,n,pos);
			}
			else
				flag[i]=1;
		}
	sort(ALL(seg),[&](const pii &a,const pii &b)
	{
		return mp(a.second,a.first)<mp(b.second,b.first);
	});
	for(auto pr:seg)
		if(query(1,1,n,pr.first,pr.second)<b)
		{
			update(1,1,n,pr.first,pr.second,1);
			vec.pb(pr.first);
		}
	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: 5628kb

input:

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

output:

9
3 6 5 8 4 10 1 12 14 

result:

ok n=14

Test #2:

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

input:

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

output:

8
3 6 5 8 4 10 12 14 

result:

ok n=14

Test #3:

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

input:

0 0

output:

0

result:

ok n=0

Test #4:

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

input:

0 1

output:

0

result:

ok n=0

Test #5:

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

input:

3 0
1 -1 2

output:

0

result:

ok n=3

Test #6:

score: 0
Accepted
time: 20ms
memory: 13508kb

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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 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: 51ms
memory: 34436kb

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
3 6 7 8 9 10 11 12 15 16 20 21 24 25 27 32 34 35 39 41 43 45 46 47 50 54 58 60 61 65 68 69 70 72 73 75 77 78 79 83 86 87 88 90 91 94 95 97 99 102 103 106 107 108 110 113 114 115 116 117 118 120 121 123 124 125 126 128 130 131 133 134 137 140 141 142 143 146 147 148 149 150 151 152 153 154 161...

result:

ok n=200000

Test #8:

score: 0
Accepted
time: 52ms
memory: 16268kb

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:

95229
3 6 10 12 16 15 21 20 19 25 27 14 9 8 5 33 40 43 47 46 45 53 58 62 64 61 67 69 74 73 77 79 72 71 83 60 86 88 91 90 95 94 57 100 105 104 103 109 114 113 112 111 120 122 126 125 129 134 136 133 132 131 141 124 144 146 149 148 119 155 157 154 161 160 153 169 172 171 176 175 179 181 168 167 166 18...

result:

ok n=200000

Test #9:

score: 0
Accepted
time: 72ms
memory: 15760kb

input:

200000 20
155567 -1 155567 131057 131057 131057 -1 131057 131057 155567 155567 -1 155567 131057 155567 131057 155567 131057 131057 -1 155567 -1 155567 155567 131057 -1 155567 131057 131057 -1 155567 -1 -1 -1 -1 155567 155567 155567 131057 155567 155567 -1 -1 155567 131057 -1 131057 155567 155567 131...

output:

122786
1 3 6 9 11 17 19 18 21 24 25 27 29 28 31 16 23 14 15 8 13 39 41 5 40 44 45 50 51 59 60 47 58 64 65 68 69 67 71 73 74 76 77 57 63 81 82 4 84 86 87 89 91 93 94 80 90 56 55 54 99 101 104 108 109 103 107 112 113 106 117 119 116 115 122 124 126 128 129 131 133 134 138 139 137 141 136 144 145 125 1...

result:

ok n=200000

Test #10:

score: 0
Accepted
time: 80ms
memory: 17520kb

input:

200000 20
138057 138873 168674 -1 138057 138873 168674 -1 168674 -1 168674 138873 168674 168674 138057 168674 168674 138057 168674 168674 168674 138057 168674 168674 -1 168674 -1 138873 138057 138873 -1 138057 -1 138873 138873 168674 138873 168674 168674 168674 168674 138057 -1 -1 138873 -1 138873 1...

output:

133363
1 2 3 5 6 7 9 12 22 24 18 26 23 29 30 21 28 32 37 41 42 15 35 40 39 45 38 47 49 58 60 61 56 57 59 48 53 55 52 54 36 70 69 74 68 73 77 78 80 67 83 84 66 88 89 82 91 92 97 98 99 79 95 96 51 102 94 104 107 108 106 111 87 110 86 114 116 34 118 121 72 120 123 119 125 126 20 129 130 19 133 134 136 ...

result:

ok n=200000

Test #11:

score: 0
Accepted
time: 7ms
memory: 5708kb

input:

200000 20
188193 86334 146424 150245 78691 79678 44101 77077 170039 43828 7101 166020 176227 41151 82724 45490 84724 79713 5501 37207 66814 185018 193607 179939 84382 163390 98015 102547 179011 165556 96161 139944 139885 161535 175730 163737 91028 94827 92339 103298 143767 30016 106267 46994 45275 1...

output:

20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 

result:

ok n=200000

Test #12:

score: 0
Accepted
time: 7ms
memory: 6188kb

input:

200000 20
171920 28552 11519 178013 116657 178824 171886 48055 141797 119693 173665 100702 4535 59719 81762 46520 51245 19480 48560 71217 128319 36157 57182 196435 83371 145679 115504 175398 166539 61340 40108 45709 103958 78783 119395 69220 99917 70471 190867 57876 141729 153517 99788 136120 168256...

output:

20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 

result:

ok n=200000

Test #13:

score: 0
Accepted
time: 78ms
memory: 51104kb

input:

200000 20
135276 122914 91880 55943 130295 110918 55421 86111 127485 25319 176493 13524 104729 21568 34610 143936 112811 127180 86366 -1 151119 55304 78348 68344 177442 74828 198628 108795 112224 188504 197456 163673 -1 136654 117930 115864 95087 32333 25501 162158 9468 149563 84257 112037 30323 358...

output:

123130
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 21 22 23 24 25 26 27 28 29 30 31 32 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 61 62 63 64 65 66 68 69 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 1...

result:

ok n=200000

Test #14:

score: 0
Accepted
time: 82ms
memory: 51044kb

input:

200000 20
179200 134876 39752 140338 17274 157441 41175 98316 144283 81278 593 91206 80890 -1 42705 8932 -1 191013 154678 11164 92355 4580 10134 20887 193937 162152 13547 22739 69246 131441 159276 7079 22780 91471 181700 190426 78687 167833 172357 175732 138953 6092 120352 161081 -1 28598 123275 104...

output:

77849
1 2 3 4 5 6 7 8 9 10 11 12 13 15 16 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 145 146 147 148 149 150 151 152 154 155 156 157 158 159 16...

result:

ok n=200000

Test #15:

score: 0
Accepted
time: 83ms
memory: 32736kb

input:

200000 20
8128 120929 188493 6288 120929 120929 5242 120929 120929 8370 164386 174157 130332 85589 145417 120929 129155 120929 103225 120929 147932 -1 120929 12772 54973 13439 199857 199555 162362 120929 -1 120929 120929 120929 -1 131466 57156 120929 120929 80279 120929 120929 94733 120929 120929 29...

output:

66158
1 3 4 7 10 11 12 13 14 15 17 19 20 21 24 25 26 27 28 29 30 34 36 37 40 43 46 47 55 58 59 60 62 63 65 68 71 73 74 75 77 79 80 81 84 87 89 90 91 150 155 156 157 158 159 160 161 163 166 167 168 170 171 177 178 179 181 185 186 188 191 192 193 194 195 196 197 198 199 200 202 205 206 207 208 210 211...

result:

ok n=200000

Test #16:

score: -100
Wrong Answer
time: 86ms
memory: 26996kb

input:

200000 20
188997 188997 188997 188997 27390 75480 188997 188997 75480 75480 7096 28941 188997 86194 188997 188997 180257 147851 75480 188997 29656 188997 168675 75480 75480 188997 188997 188997 166644 75480 21560 188997 75480 75480 145689 188997 82666 7981 188997 138329 75480 131526 120737 188997 20...

output:

58891
5 11 12 14 17 18 21 23 29 31 35 37 38 40 42 43 45 51 53 55 73 75 83 88 89 91 96 97 101 104 105 107 108 109 110 113 115 118 122 128 132 134 137 138 140 143 146 150 152 156 158 159 161 162 163 176 178 180 181 182 184 185 187 189 196 197 199 200 203 205 206 207 209 218 224 226 228 232 233 237 239...

result:

wrong answer Buffer overflowed