QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#220722#6553. Shared Memory Switchucup-team191#TL 80ms40252kbC++141.4kb2023-10-20 18:49:072023-10-20 18:49:07

Judging History

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

  • [2023-10-20 18:49:07]
  • 评测
  • 测评结果:TL
  • 用时:80ms
  • 内存:40252kb
  • [2023-10-20 18:49:07]
  • 提交

answer

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
using ll=long long;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
using vi=vector<int>;
using vl=vector<ll>;
#define pb push_back
#define all(a) begin(a),end(a)

const int N=300010,MOD=1e9+7;
const char en='\n';
const ll LLINF=1ll<<60;

int n,k,h[N],gr[N];
vi im[N];
set<int> zar[N];

int getNex(int x,int i)
{
	auto it=upper_bound(all(im[x]),i);
	if (it==im[x].end()) return -1;
	return *it;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>k;
	for (int i=0;i<n;++i)
	{
		cin>>h[i];
		if (h[i]==-1) h[i]=0;
		im[h[i]].pb(i);
	}
	for (int a=1;a<=n;++a)
	{
		vi st;
		for (auto x: im[a])
		{
			st.pb(x);
			int ne=getNex(a,x),n0=getNex(0,x);
			while (n0!=-1 && (ne==-1 || n0<ne))
			{
				if (st.size())
				{
					gr[st.back()]=n0;
					st.pop_back();
				}
				n0=getNex(0,n0);
			}
		}
		for (auto x: st) gr[x]=n;
	}
	set<pii> cu; //r,l
	set<int> uz;
	for (int i=0;i<n;++i) if (h[i]) uz.insert(i);
	for (int i=0;i<n;++i)
	{
		if (h[i])
		{
			cu.insert({gr[i],i});
			zar[gr[i]].insert(i);
			if ((int)cu.size()>k)
			{
				int mak=cu.rbegin()->y;
				cu.erase({gr[mak],mak});
				zar[gr[mak]].erase(mak);
				uz.erase(mak);
			}
		}
		else
		{
			for (auto x: zar[i]) cu.erase({gr[x],x});
		}
	}
	cout<<uz.size()<<en;
	for (auto x: uz) cout<<x+1<<' ';
	cout<<en;
}

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 25780kb

input:

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

output:

9
1 3 4 5 6 8 10 12 14 

result:

ok n=14

Test #2:

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

input:

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

output:

8
3 4 5 6 8 10 12 14 

result:

ok n=14

Test #3:

score: 0
Accepted
time: 4ms
memory: 25564kb

input:

0 0

output:

0


result:

ok n=0

Test #4:

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

input:

0 1

output:

0


result:

ok n=0

Test #5:

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

input:

3 0
1 -1 2

output:

0


result:

ok n=3

Test #6:

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

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 4 6 9 10 12 13 14 16 17 18 19 20 21 22 23 24 25 27 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: -100
Time Limit Exceeded

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:


result: