QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#358934 | #6553. Shared Memory Switch | Kevin5307 | TL | 31ms | 16392kb | C++20 | 2.2kb | 2024-03-20 09:10:37 | 2024-03-20 09:10:38 |
Judging History
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
#define ls (x<<1)
#define rs (ls|1)
void die(string S){puts(S.c_str());exit(0);}
int used[200200];
int q[200200];
bool flag[200200];
int delta[200200];
vector<int> st[200200];
int mx[200200<<2],tag[200200<<2];
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];
}
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++;
for(int x=1;x<=n;x++)
st[x].pb(i);
}
else
{
if(used[q[i]]<s&&query(1,1,n,i,st[q[i]].back()-1)<b)
{
vec.pb(i);
used[q[i]]++;
delta[i]++;
delta[st[q[i]].back()]--;
update(1,1,n,i,st[q[i]].back()-1,1);
st[q[i]].pop_back();
}
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: 0ms
memory: 3784kb
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: 3568kb
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: 1ms
memory: 3480kb
input:
0 0
output:
0
result:
ok n=0
Test #4:
score: 0
Accepted
time: 1ms
memory: 3528kb
input:
0 1
output:
0
result:
ok n=0
Test #5:
score: 0
Accepted
time: 0ms
memory: 3444kb
input:
3 0 1 -1 2
output:
0
result:
ok n=3
Test #6:
score: 0
Accepted
time: 31ms
memory: 16392kb
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: -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 -...