QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#358939 | #6553. Shared Memory Switch | Kevin5307 | WA | 75ms | 32524kb | C++20 | 2.8kb | 2024-03-20 09:20:20 | 2024-03-20 09:20:20 |
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
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;
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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3816kb
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: 0ms
memory: 3564kb
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: 3484kb
input:
0 0
output:
0
result:
ok n=0
Test #4:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
0 1
output:
0
result:
ok n=0
Test #5:
score: 0
Accepted
time: 0ms
memory: 3824kb
input:
3 0 1 -1 2
output:
0
result:
ok n=3
Test #6:
score: 0
Accepted
time: 14ms
memory: 5560kb
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: 47ms
memory: 32524kb
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: 0
Accepted
time: 48ms
memory: 12332kb
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 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:
ok n=200000
Test #9:
score: 0
Accepted
time: 56ms
memory: 12936kb
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 199997 199995 199994 199992 199988 199987 199986 199983 199981 199980 199979 199977 199975 199974 199973 199971 199969 199968 199967 199965 199964 199963 199960 199957 199954 199953 199950 199949 199948 199947 199946 199944 199943 199940 199939 199936 199935 199934 199930 199927 199926 199925...
result:
ok n=200000
Test #10:
score: -100
Wrong Answer
time: 75ms
memory: 13576kb
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:
133362 199999 199997 199992 199987 199985 199984 199981 199978 199976 199974 199973 199972 199969 199968 199967 199966 199965 199964 199963 199962 199960 199957 199956 199955 199954 199952 199951 199950 199949 199948 199947 199946 199945 199944 199943 199941 199939 199938 199937 199936 199935 199934...
result:
wrong answer Jury's answer is strictly better