QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#220722 | #6553. Shared Memory Switch | ucup-team191# | TL | 80ms | 40252kb | C++14 | 1.4kb | 2023-10-20 18:49:07 | 2023-10-20 18:49:07 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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 -...