提出 #63543511


ソースコード 拡げる

#include<bits/stdc++.h>
#define mid ((lf+rt)>>1)
using namespace std;
inline long long read()
{
	long long t=0,f=1;char h=getchar();
	while(!isdigit(h)){if(h=='-')f=-1;h=getchar();}
	while(isdigit(h))t=(t<<1)+(t<<3)+(h^48),h=getchar();
	return t*f;
}
void write(long long x)
{
	if(x<0)putchar('-'),x=-x;if(x>9)write(x/10);putchar(x%10+'0');
}
const int N=2e5+10;
const int inf=2e5;
int n,m;
vector<int>v[N];
int num[N*4];
void upd(int x,int p,int lf,int rt)
{
	++num[p];
	if(lf==rt)return;
	if(x<=mid)upd(x,p<<1,lf,mid);
	else upd(x,p<<1|1,mid+1,rt);
}
int que(int l,int r,int p,int lf,int rt)
{
	if(l<=lf&&rt<=r)return num[p];
	int val=0;
	if(l<=mid)val=que(l,r,p<<1,lf,mid);
	if(r>mid)val+=que(l,r,p<<1|1,mid+1,rt);
	return val;
}
int a[N];
long long ans=0;
int main()
{
	n=read();m=read();
	for(int i=1;i<=n;i++)
	{
		a[i]=read(),v[a[i]].push_back(i);
		upd(a[i],1,0,inf);
		if(a[i]<inf)ans+=que(a[i]+1,inf,1,0,inf);
//		cout<<ans<<endl;
	}
	for(int i=0;i<m;i++)
	{
//		cout<<"---";
		write(ans);puts("");
		int tmp=v[m-i-1].size(),tt=tmp;
//		for(auto x:v[m-i])
		for(int s=0;s<tmp;s++)
		{
			int x=v[m-i-1][s];
//			cout<<x<<endl;
			--tt;
			ans-=n-x-tt;
			ans+=x-1-(tmp-tt-1);
		}
	}
	return 0;
}

提出情報

提出日時
問題 F - Rotated Inversions
ユーザ baiguifan_
言語 C++ 20 (gcc 12.2)
得点 500
コード長 1267 Byte
結果 AC
実行時間 110 ms
メモリ 17304 KiB

コンパイルエラー

Main.cpp: In function ‘void write(long long int)’:
Main.cpp:13:9: warning: this ‘if’ clause does not guard... [-Wmisleading-indentation]
   13 |         if(x<0)putchar('-'),x=-x;if(x>9)write(x/10);putchar(x%10+'0');
      |         ^~
Main.cpp:13:34: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the ‘if’
   13 |         if(x<0)putchar('-'),x=-x;if(x>9)write(x/10);putchar(x%10+'0');
      |                                  ^~

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 500 / 500
結果
AC × 3
AC × 31
セット名 テストケース
Sample 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt
All 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 01_handmade_00.txt, 01_handmade_01.txt, 01_handmade_02.txt, 01_handmade_03.txt, 01_handmade_04.txt, 01_handmade_05.txt, 01_handmade_06.txt, 02_random_00.txt, 02_random_01.txt, 02_random_02.txt, 02_random_03.txt, 02_random_04.txt, 02_random_05.txt, 02_random_06.txt, 02_random_07.txt, 02_random_08.txt, 02_random_09.txt, 02_random_10.txt, 02_random_11.txt, 02_random_12.txt, 02_random_13.txt, 02_random_14.txt, 02_random_15.txt, 02_random_16.txt, 02_random_17.txt, 02_random_18.txt, 02_random_19.txt, 02_random_20.txt
ケース名 結果 実行時間 メモリ
00_sample_00.txt AC 2 ms 3564 KiB
00_sample_01.txt AC 2 ms 3528 KiB
00_sample_02.txt AC 2 ms 3580 KiB
01_handmade_00.txt AC 2 ms 3652 KiB
01_handmade_01.txt AC 7 ms 3576 KiB
01_handmade_02.txt AC 45 ms 17180 KiB
01_handmade_03.txt AC 47 ms 17304 KiB
01_handmade_04.txt AC 110 ms 17248 KiB
01_handmade_05.txt AC 109 ms 17244 KiB
01_handmade_06.txt AC 109 ms 17292 KiB
02_random_00.txt AC 73 ms 13696 KiB
02_random_01.txt AC 41 ms 12048 KiB
02_random_02.txt AC 16 ms 10512 KiB
02_random_03.txt AC 15 ms 9964 KiB
02_random_04.txt AC 19 ms 10600 KiB
02_random_05.txt AC 103 ms 14896 KiB
02_random_06.txt AC 103 ms 14936 KiB
02_random_07.txt AC 103 ms 15144 KiB
02_random_08.txt AC 102 ms 15092 KiB
02_random_09.txt AC 103 ms 14968 KiB
02_random_10.txt AC 30 ms 5324 KiB
02_random_11.txt AC 27 ms 5064 KiB
02_random_12.txt AC 29 ms 4984 KiB
02_random_13.txt AC 29 ms 5236 KiB
02_random_14.txt AC 30 ms 5444 KiB
02_random_15.txt AC 29 ms 5092 KiB
02_random_16.txt AC 30 ms 5264 KiB
02_random_17.txt AC 28 ms 5020 KiB
02_random_18.txt AC 30 ms 5220 KiB
02_random_19.txt AC 31 ms 5276 KiB
02_random_20.txt AC 49 ms 14964 KiB