Submission #936525

#	Time	Username	Problem	Language	Result	Execution time	Memory
936525		dshfjka	Swap Swap Sort (CCO21_day1problem1)	C++14	25 / 25	2566 ms	57420 KiB

Main

#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 (stderr)

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);
      |      ~~~~~^~~~~~~~~~~

• Subtask 1: 3 / 3
• Subtask 2: 3 / 3
• Subtask 3: 5 / 5
• Subtask 4: 14 / 14