# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
936522 | dshfjka | Swap Swap Sort (CCO21_day1problem1) | C++14 | 191 ms | 19152 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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[n+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];
for(LL b=1;b<=n;b++)
{
tmp[b]=tmp[a-1];
if(arr[b]==a)tmp[b]++;
}
for(LL b=1;b<=k;b++)
{
LL tot=0;
for(LL x:pos[b])tot+=tmp[x];
v[a].push_back(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);
}
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |