oj.uz

Submission #936522

# Submission time Handle Problem Language Result Execution time Memory
936522 2024-03-02T04:40:12 Z dshfjka Swap Swap Sort (CCO21_day1problem1) C++14
0 / 25
 191 ms 19152 KB 
#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);
    }
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:88: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]
   88 |        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:75:11: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |      scanf("%lld",&x);
      |      ~~~~~^~~~~~~~~~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 2 ms 604 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 6096 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 191 ms 19152 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 2 ms 604 KB Output isn't correct
3 Halted 0 ms 0 KB -