提出 #42235100


ソースコード 拡げる

#include<cstdio>
#include<cstring>
#include<deque>
#define N 210000
#define NN 410000
#define fep(i,x,y) for(int i=x;i<=y;i++)
#define feq(i,x,y) for(int i=x;i>=y;i--)
using namespace std;
typedef long long LL;
const LL mod=998244353;
struct node{
	LL d/*差值*/;//上减下 
	int siz;
	node(LL td){d=td;}
	node(LL td,int ts){d=td;siz=ts;}
};LL zsum=0,ans=0,cnt=0;
inline bool operator<(node x,node y){return x.d<y.d;}
inline bool operator>(node x,node y){return x.d>y.d;}
deque<node> fuck;
int n;LL la,lb;//lazy标记 
LL fa[N],fb[N];
inline LL zheng(LL x){return (x%mod+mod)%mod;}
int main(){
	scanf("%d",&n);
	fep(i,1,n)scanf("%lld",&fa[i]);
	fep(i,1,n)scanf("%lld",&fb[i]);
	fep(i,1,n){
		LL ta=fa[i],tb=fb[i];cnt=(cnt+ta+tb)%mod;
		//初次处理。
		la+=ta;lb+=tb;
		node cel=node(-tb-la+lb,1),flo=node(ta-la+lb,1);
		zsum+=(i+i-2)*(ta+tb);zsum=(zsum+ta*3+tb*3)%mod;
		deque<node>::iterator x=fuck.begin();
		while(x!=fuck.end() && (x->d)+la-lb<=-tb){
			zsum-=(-((x->d)+la-lb)-tb)%mod*x->siz;zsum=(zsum%mod+mod)%mod;
			cel.siz+=x->siz;x++;fuck.pop_front();
		}
		x=fuck.end();
		if(x!=fuck.begin()){
			x--;
			while((x->d)+la-lb>=ta){
				zsum-=(((x->d)+la-lb)-ta)%mod*x->siz;zsum=(zsum%mod+mod)%mod;
				flo.siz+=x->siz;
				if(x!=fuck.begin()){x--;fuck.pop_back();}
				else {fuck.pop_back();break;}
			}
		}
		fuck.push_front(cel);fuck.push_back(flo);
		ans=(ans+zsum)%mod;
	}
	printf("%lld\n",zheng((ans-cnt)*2-cnt));
	return 0;
}

提出情報

提出日時
問題 E - All Pair Shortest Paths
ユーザ juruozjj
言語 C++ (GCC 9.2.1)
得点 800
コード長 1497 Byte
結果 AC
実行時間 65 ms
メモリ 12732 KiB

コンパイルエラー

./Main.cpp: In function ‘int main()’:
./Main.cpp:24:7: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   24 |  scanf("%d",&n);
      |  ~~~~~^~~~~~~~~
./Main.cpp:25:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   25 |  fep(i,1,n)scanf("%lld",&fa[i]);
      |            ~~~~~^~~~~~~~~~~~~~~
./Main.cpp:26:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   26 |  fep(i,1,n)scanf("%lld",&fb[i]);
      |            ~~~~~^~~~~~~~~~~~~~~

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 800 / 800
結果
AC × 3
AC × 74
セット名 テストケース
Sample 01_sample_01.txt, 01_sample_02.txt, 01_sample_03.txt
All 01_sample_01.txt, 01_sample_02.txt, 01_sample_03.txt, 02_small_01.txt, 02_small_02.txt, 02_small_03.txt, 02_small_04.txt, 02_small_05.txt, 02_small_06.txt, 02_small_07.txt, 02_small_08.txt, 02_small_09.txt, 02_small_10.txt, 03_rand_1_01.txt, 03_rand_1_02.txt, 03_rand_1_03.txt, 03_rand_1_04.txt, 03_rand_1_05.txt, 03_rand_1_06.txt, 03_rand_1_07.txt, 03_rand_1_08.txt, 03_rand_1_09.txt, 03_rand_1_10.txt, 04_rand_2_01.txt, 04_rand_2_02.txt, 04_rand_2_03.txt, 04_rand_2_04.txt, 04_rand_2_05.txt, 04_rand_2_06.txt, 04_rand_2_07.txt, 04_rand_2_08.txt, 04_rand_2_09.txt, 04_rand_2_10.txt, 05_max_ans_01.txt, 06_rand_3_01.txt, 06_rand_3_02.txt, 06_rand_3_03.txt, 06_rand_3_04.txt, 06_rand_3_05.txt, 06_rand_3_06.txt, 06_rand_3_07.txt, 06_rand_3_08.txt, 06_rand_3_09.txt, 06_rand_3_10.txt, 07_rand_4_01.txt, 07_rand_4_02.txt, 07_rand_4_03.txt, 07_rand_4_04.txt, 07_rand_4_05.txt, 07_rand_4_06.txt, 07_rand_4_07.txt, 07_rand_4_08.txt, 07_rand_4_09.txt, 07_rand_4_10.txt, 08_rand_5_01.txt, 08_rand_5_02.txt, 08_rand_5_03.txt, 08_rand_5_04.txt, 08_rand_5_05.txt, 08_rand_5_06.txt, 08_rand_5_07.txt, 08_rand_5_08.txt, 08_rand_5_09.txt, 08_rand_5_10.txt, 09_rand_6_01.txt, 09_rand_6_02.txt, 09_rand_6_03.txt, 09_rand_6_04.txt, 09_rand_6_05.txt, 09_rand_6_06.txt, 09_rand_6_07.txt, 09_rand_6_08.txt, 09_rand_6_09.txt, 09_rand_6_10.txt
ケース名 結果 実行時間 メモリ
01_sample_01.txt AC 5 ms 3204 KiB
01_sample_02.txt AC 3 ms 3120 KiB
01_sample_03.txt AC 2 ms 3112 KiB
02_small_01.txt AC 2 ms 3084 KiB
02_small_02.txt AC 2 ms 3116 KiB
02_small_03.txt AC 2 ms 3228 KiB
02_small_04.txt AC 2 ms 3116 KiB
02_small_05.txt AC 2 ms 3120 KiB
02_small_06.txt AC 2 ms 3228 KiB
02_small_07.txt AC 4 ms 3204 KiB
02_small_08.txt AC 2 ms 3204 KiB
02_small_09.txt AC 2 ms 3188 KiB
02_small_10.txt AC 2 ms 3180 KiB
03_rand_1_01.txt AC 61 ms 6256 KiB
03_rand_1_02.txt AC 59 ms 6236 KiB
03_rand_1_03.txt AC 61 ms 6236 KiB
03_rand_1_04.txt AC 63 ms 6240 KiB
03_rand_1_05.txt AC 62 ms 6336 KiB
03_rand_1_06.txt AC 60 ms 6232 KiB
03_rand_1_07.txt AC 62 ms 6232 KiB
03_rand_1_08.txt AC 59 ms 6324 KiB
03_rand_1_09.txt AC 61 ms 6224 KiB
03_rand_1_10.txt AC 62 ms 6312 KiB
04_rand_2_01.txt AC 55 ms 6312 KiB
04_rand_2_02.txt AC 54 ms 6336 KiB
04_rand_2_03.txt AC 54 ms 6312 KiB
04_rand_2_04.txt AC 55 ms 6256 KiB
04_rand_2_05.txt AC 54 ms 6348 KiB
04_rand_2_06.txt AC 55 ms 6348 KiB
04_rand_2_07.txt AC 53 ms 6340 KiB
04_rand_2_08.txt AC 54 ms 6256 KiB
04_rand_2_09.txt AC 55 ms 6236 KiB
04_rand_2_10.txt AC 55 ms 6304 KiB
05_max_ans_01.txt AC 65 ms 6320 KiB
06_rand_3_01.txt AC 59 ms 12696 KiB
06_rand_3_02.txt AC 60 ms 12708 KiB
06_rand_3_03.txt AC 64 ms 12732 KiB
06_rand_3_04.txt AC 59 ms 12600 KiB
06_rand_3_05.txt AC 61 ms 12712 KiB
06_rand_3_06.txt AC 62 ms 12732 KiB
06_rand_3_07.txt AC 61 ms 12628 KiB
06_rand_3_08.txt AC 61 ms 6200 KiB
06_rand_3_09.txt AC 61 ms 12700 KiB
06_rand_3_10.txt AC 63 ms 6232 KiB
07_rand_4_01.txt AC 61 ms 9592 KiB
07_rand_4_02.txt AC 62 ms 9568 KiB
07_rand_4_03.txt AC 61 ms 9496 KiB
07_rand_4_04.txt AC 61 ms 9492 KiB
07_rand_4_05.txt AC 61 ms 9496 KiB
07_rand_4_06.txt AC 61 ms 9588 KiB
07_rand_4_07.txt AC 62 ms 9576 KiB
07_rand_4_08.txt AC 62 ms 9496 KiB
07_rand_4_09.txt AC 62 ms 9596 KiB
07_rand_4_10.txt AC 62 ms 9600 KiB
08_rand_5_01.txt AC 60 ms 6324 KiB
08_rand_5_02.txt AC 60 ms 6320 KiB
08_rand_5_03.txt AC 60 ms 6340 KiB
08_rand_5_04.txt AC 63 ms 8472 KiB
08_rand_5_05.txt AC 59 ms 6324 KiB
08_rand_5_06.txt AC 59 ms 6236 KiB
08_rand_5_07.txt AC 58 ms 6224 KiB
08_rand_5_08.txt AC 59 ms 9004 KiB
08_rand_5_09.txt AC 58 ms 6200 KiB
08_rand_5_10.txt AC 61 ms 7760 KiB
09_rand_6_01.txt AC 58 ms 8880 KiB
09_rand_6_02.txt AC 62 ms 8344 KiB
09_rand_6_03.txt AC 61 ms 7908 KiB
09_rand_6_04.txt AC 60 ms 7612 KiB
09_rand_6_05.txt AC 61 ms 8952 KiB
09_rand_6_06.txt AC 61 ms 8980 KiB
09_rand_6_07.txt AC 63 ms 7564 KiB
09_rand_6_08.txt AC 59 ms 8352 KiB
09_rand_6_09.txt AC 60 ms 7084 KiB
09_rand_6_10.txt AC 60 ms 6980 KiB