提出 #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 | ||||
| 結果 |
|
|
| セット名 | テストケース |
|---|---|
| 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 |