QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #486918 | #6701. BaoBao Loves Reading | priudy | AC ✓ | 215ms | 7740kb | C++14 | 1.0kb | 2024-07-22 11:49:18 | 2024-07-22 11:49:19 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=200005;
int n,m;
int pre[N],tree[N],ans[N];
int lowbit(int t){
return t & (-t);
}
void add(int x,int v){
while(x<=n){
tree[x]+=v;
x+=(lowbit(x));
}
}
int ask(int x){
int sum=0;
while(x){
sum+=tree[x];
x-=lowbit(x);
}
return sum;
}
void init(){
for(int i=0;i<=n;i++)
pre[i]=tree[i]=ans[i]=0;
}
void solve(){
cin>>n;
init();int tmp;
for(int i=1;i<=n;i++){
cin>>tmp;
if(pre[tmp]){
add(pre[tmp],-1);
add(i,1);
int len=ask(i)-ask(pre[tmp]-1);
ans[len]++;
pre[tmp]=i;
}
else{
pre[tmp]=i;
add(pre[tmp],1);
}
}
for(int i=1;i<=n;i++){
ans[i]+=ans[i-1];
if(i==1)cout<<n-ans[i];
else cout<<" "<<n-ans[i];
}cout<<endl;
return;
}
signed main() {
//ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int t=1;
cin>>t;
while(t--){
solve();
}
return 0;
}
这程序好像有点Bug，我给组数据试试？
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5692kb
input:
1 7 4 3 4 2 3 1 4
output:
7 6 5 4 4 4 4
result:
ok single line: '7 6 5 4 4 4 4'
Test #2:
score: 0
Accepted
time: 2ms
memory: 7740kb
input:
100 73 45 45 2 2 2 45 35 45 16 35 16 45 35 2 16 16 45 2 45 45 16 35 35 16 35 35 2 2 2 35 45 35 45 35 16 35 2 2 16 35 16 45 45 16 45 2 16 16 35 16 45 16 45 45 16 16 35 35 35 35 45 45 45 35 16 16 16 2 16 16 35 16 2 83 78 52 7 35 33 82 51 27 45 34 17 51 55 25 26 11 52 41 25 41 13 46 33 83 83 7 40 51 33...
output:
51 30 17 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 80 77 74 73 69 68 66 64 61 61 59 56 53 49 47 47 44 42 39 38 36 36 34 33 30 29 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 2...
result:
ok 100 lines
Test #3:
score: 0
Accepted
time: 215ms
memory: 7100kb
input:
1117 72 27 62 37 62 21 71 27 62 37 37 21 21 62 71 27 37 62 37 21 71 27 21 27 71 71 62 71 62 62 37 27 37 71 62 62 37 71 62 71 71 37 27 21 71 21 27 27 62 27 71 62 21 27 37 21 21 71 37 21 37 21 37 27 21 71 62 37 37 62 37 21 27 88 58 48 19 47 46 50 4 78 11 68 80 29 4 3 88 49 54 25 78 47 78 45 34 54 4 46...
output:
63 49 36 23 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 86 84 83 82 81 78 75 72 71 69 65 64 62 60 60 59 57 53 53 52 50 48 46 45 44 42 42 41 40 40 40 40 39 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38...
result:
ok 1117 lines