QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #706626 | #6701. BaoBao Loves Reading | futarian# | AC ✓ | 116ms | 5800kb | C++14 | 977b | 2024-11-03 12:41:54 | 2024-11-03 12:41:54 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int Len = 1e5 + 5;
int a[Len],n,pre[Len],b[Len],sum[Len];
#define lowbit(x) (x & (-x))
int c[Len];
inline void add(int x,int ad)
{
while(x <= n)
{
c[x] += ad;
x += lowbit(x);
}
}
inline int qry(int x)
{
int res = 0;
while(x)
{
res += c[x];
x -= lowbit(x);
}
return res;
}
int main()
{
int T;scanf("%d",&T);
for(int j = 1 ; j <= T ; j ++)
{
scanf("%d",&n);sum[0] = 0;
for(int i = 1 ; i <= n ; i ++)
{
scanf("%d",&a[i]);c[i] = 0;
sum[i] = b[i] = 0;
pre[a[i]] = 0;
}
for(int i = 1 ; i <= n ; i ++)
{
if(pre[a[i]]) add(pre[a[i]] , -1);
add(i , 1);
if(pre[a[i]])
{
b[i] = qry(i) - qry(pre[a[i]]);
sum[b[i]] ++;
}
pre[a[i]] = i;
}
for(int i = 1 ; i <= n ; i ++) sum[i] += sum[i - 1];
for(int i = 1 ; i < n ; i ++) printf("%d ",n - sum[i]);
printf("%d",n - sum[n]);
if(j != T) puts("");
}
return 0;
}
这程序好像有点Bug，我给组数据试试？
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3860kb
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: 1ms
memory: 3988kb
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: 116ms
memory: 5800kb
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