#include <bits/stdc++.h>
#define LL long long
using namespace std;
const LL N=1e5+5;
LL n,k,q,srt;
LL sum[N+5];
void add(LL x)
{
for(LL a=x;a<=k;a+=(a&-a))
{
sum[a]++;
// printf("sum[%lld]++\n",a);
}
}
LL query(LL x)
{
LL tot=0;
for(LL a=x;a>0;a-=(a&-a))tot+=sum[a];
return tot;
}
LL query(LL x, LL y)
{
return query(y)-query(x-1);
}
int main()
{
scanf("%lld %lld %lld",&n,&k,&q);
LL arr[n+5],cnt[k+5];
memset(cnt,0,sizeof(cnt));
vector<LL>pos[k+5];
for(LL a=1;a<=n;a++)
{
scanf("%lld",&arr[a]);
pos[arr[a]].push_back(a);
}
for(LL a=1;a<=n;a++)
{
cnt[arr[a]]++;
}
LL now=0;
for(LL a=1;a<=n;a++)
{
now+=query(arr[a]+1,k);
add(arr[a]);
// printf("now =%lld\n",now);
}
// printf("now=%lld\n",now);
LL srt=sqrt(n);
vector<LL>v[n+5];
for(LL a=1;a<=k;a++)
{
if(cnt[a]>srt)
{
// printf("MASUK\n");
LL tmp[n+5];
tmp[0]=0;
for(LL b=1;b<=n;b++)
{
tmp[b]=tmp[b-1];
if(arr[b]==a)tmp[b]++;
}
for(LL b=1;b<=k;b++)
{
LL tot=0;
for(LL x:pos[b])
{
// printf("%lld+=%lld\n",tot,tmp[x]);
tot+=tmp[x];
}
// printf("%lld %lld %lld\n",tot,cnt[a],cnt[b]);
v[a].push_back(2*tot-cnt[a]*cnt[b]);
// printf("v[%lld].push_back(%lld)\n",a,2*tot-cnt[a]*cnt[b]);
}
}
}
LL brr[k+5];
for(LL a=1;a<=k;a++)brr[a]=a;
for(LL a=1;a<=q;a++)
{
LL x;
scanf("%lld",&x);
if(cnt[brr[x]]>srt || cnt[brr[x+1]]>srt)
{
if(cnt[brr[x]]>cnt[brr[x+1]])now+=v[brr[x]][brr[x+1]-1];
else now-=v[brr[x+1]][brr[x]-1];
}
else{
// printf("a=%lld\n",a);
LL left=0,tot=0;
// printf("SWAP(%lld %lld)\n",brr[x],brr[x+1]);
for(LL b:pos[brr[x]])
{
while(left<pos[brr[x+1]].size() && pos[brr[x+1]][left]<b)
{
// printf("left = %lld\n",left);
left++;
}
tot+=left;
}
now-=(2*tot-cnt[brr[x]]*cnt[brr[x+1]]);
}
swap(brr[x],brr[x+1]);
printf("%lld\n",now);
}
}
/*
5 2 3
1 2 2 2 2
1
*/
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:96:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
96 | while(left<pos[brr[x+1]].size() && pos[brr[x+1]][left]<b)
| ~~~~^~~~~~~~~~~~~~~~~~~~~
Main.cpp:27:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
27 | scanf("%lld %lld %lld",&n,&k,&q);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:33:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
33 | scanf("%lld",&arr[a]);
| ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:83:11: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
83 | scanf("%lld",&x);
| ~~~~~^~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
2 ms |
764 KB |
Output is correct |
3 |
Correct |
2 ms |
856 KB |
Output is correct |
4 |
Correct |
2 ms |
856 KB |
Output is correct |
5 |
Correct |
4 ms |
600 KB |
Output is correct |
6 |
Correct |
2 ms |
600 KB |
Output is correct |
7 |
Correct |
2 ms |
604 KB |
Output is correct |
8 |
Correct |
2 ms |
996 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
5216 KB |
Output is correct |
2 |
Correct |
10 ms |
5324 KB |
Output is correct |
3 |
Correct |
46 ms |
5608 KB |
Output is correct |
4 |
Correct |
12 ms |
4956 KB |
Output is correct |
5 |
Correct |
15 ms |
5432 KB |
Output is correct |
6 |
Correct |
19 ms |
5720 KB |
Output is correct |
7 |
Correct |
20 ms |
8028 KB |
Output is correct |
8 |
Correct |
26 ms |
10836 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
173 ms |
16312 KB |
Output is correct |
2 |
Correct |
185 ms |
18340 KB |
Output is correct |
3 |
Correct |
188 ms |
19100 KB |
Output is correct |
4 |
Correct |
203 ms |
19540 KB |
Output is correct |
5 |
Correct |
2500 ms |
20024 KB |
Output is correct |
6 |
Correct |
2043 ms |
19856 KB |
Output is correct |
7 |
Correct |
2041 ms |
19648 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
2 ms |
764 KB |
Output is correct |
3 |
Correct |
2 ms |
856 KB |
Output is correct |
4 |
Correct |
2 ms |
856 KB |
Output is correct |
5 |
Correct |
4 ms |
600 KB |
Output is correct |
6 |
Correct |
2 ms |
600 KB |
Output is correct |
7 |
Correct |
2 ms |
604 KB |
Output is correct |
8 |
Correct |
2 ms |
996 KB |
Output is correct |
9 |
Correct |
10 ms |
5216 KB |
Output is correct |
10 |
Correct |
10 ms |
5324 KB |
Output is correct |
11 |
Correct |
46 ms |
5608 KB |
Output is correct |
12 |
Correct |
12 ms |
4956 KB |
Output is correct |
13 |
Correct |
15 ms |
5432 KB |
Output is correct |
14 |
Correct |
19 ms |
5720 KB |
Output is correct |
15 |
Correct |
20 ms |
8028 KB |
Output is correct |
16 |
Correct |
26 ms |
10836 KB |
Output is correct |
17 |
Correct |
173 ms |
16312 KB |
Output is correct |
18 |
Correct |
185 ms |
18340 KB |
Output is correct |
19 |
Correct |
188 ms |
19100 KB |
Output is correct |
20 |
Correct |
203 ms |
19540 KB |
Output is correct |
21 |
Correct |
2500 ms |
20024 KB |
Output is correct |
22 |
Correct |
2043 ms |
19856 KB |
Output is correct |
23 |
Correct |
2041 ms |
19648 KB |
Output is correct |
24 |
Correct |
1135 ms |
20004 KB |
Output is correct |
25 |
Correct |
716 ms |
20660 KB |
Output is correct |
26 |
Correct |
414 ms |
21468 KB |
Output is correct |
27 |
Correct |
322 ms |
21884 KB |
Output is correct |
28 |
Correct |
328 ms |
22900 KB |
Output is correct |
29 |
Correct |
259 ms |
24916 KB |
Output is correct |
30 |
Correct |
268 ms |
27928 KB |
Output is correct |
31 |
Correct |
290 ms |
27784 KB |
Output is correct |
32 |
Correct |
203 ms |
37316 KB |
Output is correct |
33 |
Correct |
2566 ms |
20068 KB |
Output is correct |
34 |
Correct |
2044 ms |
19712 KB |
Output is correct |
35 |
Correct |
1759 ms |
19896 KB |
Output is correct |
36 |
Correct |
1141 ms |
20560 KB |
Output is correct |
37 |
Correct |
709 ms |
20788 KB |
Output is correct |
38 |
Correct |
546 ms |
21080 KB |
Output is correct |
39 |
Correct |
252 ms |
27732 KB |
Output is correct |
40 |
Correct |
248 ms |
34052 KB |
Output is correct |
41 |
Correct |
250 ms |
38724 KB |
Output is correct |
42 |
Correct |
233 ms |
43032 KB |
Output is correct |
43 |
Correct |
249 ms |
47048 KB |
Output is correct |
44 |
Correct |
270 ms |
57420 KB |
Output is correct |
45 |
Correct |
270 ms |
54124 KB |
Output is correct |
46 |
Correct |
353 ms |
27108 KB |
Output is correct |
47 |
Correct |
463 ms |
26912 KB |
Output is correct |
48 |
Correct |
890 ms |
27252 KB |
Output is correct |
49 |
Correct |
697 ms |
26516 KB |
Output is correct |
50 |
Correct |
213 ms |
35108 KB |
Output is correct |
51 |
Correct |
203 ms |
35524 KB |
Output is correct |
52 |
Correct |
210 ms |
35304 KB |
Output is correct |
53 |
Correct |
212 ms |
33452 KB |
Output is correct |
54 |
Correct |
220 ms |
33564 KB |
Output is correct |
55 |
Correct |
0 ms |
344 KB |
Output is correct |