QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #143459 | #6701. BaoBao Loves Reading | qzez# | AC ✓ | 132ms | 5488kb | C++14 | 1.2kb | 2023-08-21 13:07:48 | 2023-08-21 13:07:51 |
Judging History
answer
#include<bits/stdc++.h>
#define Gc() getchar()
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
using namespace std;using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned long long;using pii=pair<int,int>;using LL=__int128;
const int N=1e5+5,M=N*4+5,K=31650,mod=998244353,Mod=mod-1;const db eps=1e-9;const int INF=1e9+7;mt19937 rnd(time(0));
int n,m,A[N],f[N],ans[N];
namespace BIT{
int f[N];
void Cl(){fill(f+1,f+n+1,0);}
void add(int x,int y){while(x<=n) f[x]+=y,x+=x&-x;}
int qry(int x){int ans=0;while(x) ans+=f[x],x-=x&-x;return ans;}
}
void Solve(){
int i,j;scanf("%d",&n);
for(i=1;i<=n;i++) scanf("%d",&A[i]);
fill(f+1,f+n+1,0);fill(ans+1,ans+n+1,0);BIT::Cl();
for(i=1;i<=n;i++){
if(f[A[i]]) {int p=BIT::qry(i)-BIT::qry(f[A[i]]);ans[p]++;BIT::add(f[A[i]],-1);}
else ans[n]++;
BIT::add(i,1);f[A[i]]=i;
}
for(i=n-1;i;i--) ans[i]+=ans[i+1];
for(i=1;i<=n;i++) printf("%d%c",ans[i]," \n"[i==n]);
}
int main(){
int t;scanf("%d",&t);while(t--) Solve();
}
这程序好像有点Bug，我给组数据试试？
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3792kb
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: 3740kb
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: 132ms
memory: 5488kb
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