QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #616783 | #8637. 搬砖 | connection | 100 ✓ | 90ms | 34372kb | C++14 | 988b | 2024-10-06 11:36:47 | 2024-10-06 11:36:47 |
Judging History
answer
// #pragma GCC optimize(1)
// #pragma GCC optimize(2)
// #pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
// #include <bits/extc++.h>
// using namespace __gnu_cxx;
// using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
#define mod ll(1e9+7)
const int N = 1e6+10;
ll a[N],cnt[N],suf[N],dp[N],n,ans,yhmm;
void pre(){
yhmm = *max_element(a+1,a+n+1);
for(int i=1;i<=n;i++) cnt[a[i]]++;
for(int i=1;i<=yhmm;i++) suf[i]=suf[i-1]+cnt[i];
}
ll getsuf(ll x,ll y){return suf[y]-suf[x-1];}
int main(){ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];pre();
for(int i=1,cnt=0;i<=yhmm;i++,cnt=0){
for(int j=1;j<=yhmm/i;j++)
dp[j]=getsuf(i*j,min((ll)(j+1)*i-1,yhmm));
for(int j=1;j<=yhmm/i;j++) cnt+=dp[j]%2;
if(cnt>2||cnt==0) continue;
if(cnt&1) ans+=dp[1]&1?dp[1]:0;
else for(int j=2;j<=yhmm/i;j++)
ans+=dp[j]*((dp[j]&1)&&(dp[j-1]&1));
}
cout<<ans<<endl;
return 0;
}
详细
Subtask #1:
score: 50
Accepted
Test #1:
score: 50
Accepted
time: 1ms
memory: 7768kb
input:
19 49 87 55 72 26 28 61 89 3 74 68 5 35 38 29 51 43 50 99
output:
164
result:
ok 1 number(s): "164"
Test #2:
score: 50
Accepted
time: 1ms
memory: 7680kb
input:
39 49 87 55 72 26 28 61 89 3 74 68 5 35 38 29 51 43 50 99 71 56 92 89 16 45 58 25 88 26 93 41 26 79 96 50 57 75 10 45
output:
453
result:
ok 1 number(s): "453"
Test #3:
score: 50
Accepted
time: 1ms
memory: 7688kb
input:
51 49 87 55 72 26 28 61 89 3 74 68 5 35 38 29 51 43 50 99 71 56 92 89 16 45 58 25 88 26 93 41 26 79 96 50 57 75 10 45 77 35 64 81 70 2 9 20 96 10 70 67
output:
459
result:
ok 1 number(s): "459"
Test #4:
score: 50
Accepted
time: 1ms
memory: 7644kb
input:
79 49 87 55 72 26 28 61 89 3 74 68 5 35 38 29 51 43 50 99 71 56 92 89 16 45 58 25 88 26 93 41 26 79 96 50 57 75 10 45 77 35 64 81 70 2 9 20 96 10 70 67 66 62 7 81 6 17 5 45 42 97 85 67 27 80 16 83 54 77 80 82 12 95 62 33 48 70 4 44
output:
822
result:
ok 1 number(s): "822"
Test #5:
score: 50
Accepted
time: 1ms
memory: 7704kb
input:
99 49 87 55 72 26 28 61 89 3 74 68 5 35 38 29 51 43 50 99 71 56 92 89 16 45 58 25 88 26 93 41 26 79 96 50 57 75 10 45 77 35 64 81 70 2 9 20 96 10 70 67 66 62 7 81 6 17 5 45 42 97 85 67 27 80 16 83 54 77 80 82 12 95 62 33 48 70 4 44 80 73 62 97 86 20 77 43 36 33 87 29 81 72 48 7 3 15 42 57
output:
1094
result:
ok 1 number(s): "1094"
Test #6:
score: 50
Accepted
time: 1ms
memory: 7632kb
input:
51 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
output:
201
result:
ok 1 number(s): "201"
Test #7:
score: 50
Accepted
time: 1ms
memory: 7764kb
input:
51 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 40 40 40 40 40 40 40 40 40 40 40
output:
271
result:
ok 1 number(s): "271"
Test #8:
score: 50
Accepted
time: 1ms
memory: 7616kb
input:
51 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51
output:
257
result:
ok 1 number(s): "257"
Test #9:
score: 50
Accepted
time: 0ms
memory: 7684kb
input:
51 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51
output:
257
result:
ok 1 number(s): "257"
Test #10:
score: 50
Accepted
time: 1ms
memory: 7644kb
input:
51 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51
output:
257
result:
ok 1 number(s): "257"
Test #11:
score: 50
Accepted
time: 1ms
memory: 7764kb
input:
99 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 52 57 53 53
output:
4010
result:
ok 1 number(s): "4010"
Test #12:
score: 50
Accepted
time: 1ms
memory: 7700kb
input:
99 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 52 57 53 53
output:
4010
result:
ok 1 number(s): "4010"
Test #13:
score: 50
Accepted
time: 1ms
memory: 7668kb
input:
99 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 52 57 53 53
output:
4010
result:
ok 1 number(s): "4010"
Test #14:
score: 50
Accepted
time: 0ms
memory: 7760kb
input:
99 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 52 57 53 53
output:
4010
result:
ok 1 number(s): "4010"
Test #15:
score: 50
Accepted
time: 2ms
memory: 7648kb
input:
99 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 52 57 53 53
output:
4010
result:
ok 1 number(s): "4010"
Test #16:
score: 50
Accepted
time: 1ms
memory: 7684kb
input:
39 51 49 51 50 50 49 18 17 16 17 18 16 62 61 62 62 62 61 7 8 9 7 9 8 31 31 31 31 33 31 2 2 3 3 3 3 1 2 1
output:
31
result:
ok 1 number(s): "31"
Test #17:
score: 50
Accepted
time: 1ms
memory: 7672kb
input:
39 51 49 51 50 50 49 18 17 16 17 18 16 62 61 62 62 62 61 7 8 9 7 9 8 31 31 31 31 33 31 2 2 3 3 3 3 1 2 1
output:
31
result:
ok 1 number(s): "31"
Test #18:
score: 50
Accepted
time: 0ms
memory: 7636kb
input:
39 51 49 51 50 50 49 18 17 16 17 18 16 62 61 62 62 62 61 7 8 9 7 9 8 31 31 31 31 33 31 2 2 3 3 3 3 1 2 1
output:
31
result:
ok 1 number(s): "31"
Test #19:
score: 50
Accepted
time: 0ms
memory: 7760kb
input:
39 51 49 51 50 50 49 18 17 16 17 18 16 62 61 62 62 62 61 7 8 9 7 9 8 31 31 31 31 33 31 2 2 3 3 3 3 1 2 1
output:
31
result:
ok 1 number(s): "31"
Test #20:
score: 50
Accepted
time: 1ms
memory: 7648kb
input:
39 51 49 51 50 50 49 18 17 16 17 18 16 62 61 62 62 62 61 7 8 9 7 9 8 31 31 31 31 33 31 2 2 3 3 3 3 1 2 1
output:
31
result:
ok 1 number(s): "31"
Subtask #2:
score: 50
Accepted
Test #21:
score: 50
Accepted
time: 50ms
memory: 28656kb
input:
199999 847249 186487 367355 618072 937226 591328 776261 362189 96203 363974 349368 378905 615535 753238 551029 549551 648843 257850 897199 780171 34956 529292 138489 164016 983045 678158 447625 770688 359626 620193 47041 723226 806679 414396 857650 260257 522075 633910 622445 618277 514235 488164 99...
output:
19467220030
result:
ok 1 number(s): "19467220030"
Test #22:
score: 50
Accepted
time: 53ms
memory: 31840kb
input:
399999 847249 186487 367355 618072 937226 591328 776261 362189 96203 363974 349368 378905 615535 753238 551029 549551 648843 257850 897199 780171 34956 529292 138489 164016 983045 678158 447625 770688 359626 620193 47041 723226 806679 414396 857650 260257 522075 633910 622445 618277 514235 488164 99...
output:
39223567497
result:
ok 1 number(s): "39223567497"
Test #23:
score: 50
Accepted
time: 66ms
memory: 32988kb
input:
557043 869967 501331 275724 734256 190231 819098 873529 999968 60258 379438 884151 780414 702116 792944 717694 256203 646762 983685 466878 791047 974051 365222 116941 104885 985271 980979 209094 161865 441500 379965 41174 311466 881295 316898 562073 587877 652347 435602 587845 712604 331391 471995 4...
output:
54592885599
result:
ok 1 number(s): "54592885599"
Test #24:
score: 50
Accepted
time: 77ms
memory: 34372kb
input:
717043 869967 501331 275724 734256 190231 819098 873529 999968 60258 379438 884151 780414 702116 792944 717694 256203 646762 983685 466878 791047 974051 365222 116941 104885 985271 980979 209094 161865 441500 379965 41174 311466 881295 316898 562073 587877 652347 435602 587845 712604 331391 471995 4...
output:
70358411631
result:
ok 1 number(s): "70358411631"
Test #25:
score: 50
Accepted
time: 88ms
memory: 34232kb
input:
837043 869967 501331 275724 734256 190231 819098 873529 999968 60258 379438 884151 780414 702116 792944 717694 256203 646762 983685 466878 791047 974051 365222 116941 104885 985271 980979 209094 161865 441500 379965 41174 311466 881295 316898 562073 587877 652347 435602 587845 712604 331391 471995 4...
output:
82029055917
result:
ok 1 number(s): "82029055917"
Test #26:
score: 50
Accepted
time: 32ms
memory: 20312kb
input:
557043 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1...
output:
21741111111
result:
ok 1 number(s): "21741111111"
Test #27:
score: 50
Accepted
time: 37ms
memory: 23056kb
input:
557043 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1...
output:
31259911111
result:
ok 1 number(s): "31259911111"
Test #28:
score: 50
Accepted
time: 43ms
memory: 28548kb
input:
557043 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1...
output:
30167800961
result:
ok 1 number(s): "30167800961"
Test #29:
score: 50
Accepted
time: 40ms
memory: 26120kb
input:
550719 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1...
output:
29486711431
result:
ok 1 number(s): "29486711431"
Test #30:
score: 50
Accepted
time: 43ms
memory: 26632kb
input:
550719 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1...
output:
29486711431
result:
ok 1 number(s): "29486711431"
Test #31:
score: 50
Accepted
time: 79ms
memory: 28604kb
input:
930719 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981...
output:
417390602138
result:
ok 1 number(s): "417390602138"
Test #32:
score: 50
Accepted
time: 90ms
memory: 31572kb
input:
930719 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981...
output:
417390602138
result:
ok 1 number(s): "417390602138"
Test #33:
score: 50
Accepted
time: 79ms
memory: 31860kb
input:
930719 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981 999981...
output:
417390602138
result:
ok 1 number(s): "417390602138"
Test #34:
score: 50
Accepted
time: 84ms
memory: 31848kb
input:
933479 999996 999996 999996 999996 999996 999996 999996 999996 999996 999996 999996 999996 999996 999996 999996 999996 999996 999996 999996 999996 999996 999996 999996 999996 999996 999996 999996 999996 999996 999996 999996 999996 999996 999996 999996 999996 999996 999996 999996 999996 999996 999996...
output:
392498847920
result:
ok 1 number(s): "392498847920"
Test #35:
score: 50
Accepted
time: 81ms
memory: 30512kb
input:
933479 999996 999996 999996 999996 999996 999996 999996 999996 999996 999996 999996 999996 999996 999996 999996 999996 999996 999996 999996 999996 999996 999996 999996 999996 999996 999996 999996 999996 999996 999996 999996 999996 999996 999996 999996 999996 999996 999996 999996 999996 999996 999996...
output:
392498847920
result:
ok 1 number(s): "392498847920"
Test #36:
score: 50
Accepted
time: 56ms
memory: 31232kb
input:
393479 642772 643079 642954 642851 643180 643125 643074 643248 643040 642781 643060 643128 642778 643159 642866 643184 642894 643107 642829 642973 642788 643116 642910 643249 643278 642789 642842 643339 642770 642848 642922 643356 643180 643037 642806 642866 642760 643040 643274 642960 643073 642932...
output:
6735060216
result:
ok 1 number(s): "6735060216"
Test #37:
score: 50
Accepted
time: 49ms
memory: 30220kb
input:
393479 642772 643079 642954 642851 643180 643125 643074 643248 643040 642781 643060 643128 642778 643159 642866 643184 642894 643107 642829 642973 642788 643116 642910 643249 643278 642789 642842 643339 642770 642848 642922 643356 643180 643037 642806 642866 642760 643040 643274 642960 643073 642932...
output:
6735060216
result:
ok 1 number(s): "6735060216"
Test #38:
score: 50
Accepted
time: 62ms
memory: 31928kb
input:
378201 949180 948990 948979 949231 949167 948915 948947 949284 949187 948945 949039 948922 949080 949020 949296 949143 949178 948878 949143 949334 949169 949096 949292 949057 949166 949368 949167 949316 949399 948884 949332 949150 949234 948882 949180 949201 948928 948926 949055 949247 949003 949225...
output:
24549909112
result:
ok 1 number(s): "24549909112"
Test #39:
score: 50
Accepted
time: 63ms
memory: 31568kb
input:
378201 949180 948990 948979 949231 949167 948915 948947 949284 949187 948945 949039 948922 949080 949020 949296 949143 949178 948878 949143 949334 949169 949096 949292 949057 949166 949368 949167 949316 949399 948884 949332 949150 949234 948882 949180 949201 948928 948926 949055 949247 949003 949225...
output:
24549909112
result:
ok 1 number(s): "24549909112"
Test #40:
score: 50
Accepted
time: 61ms
memory: 31504kb
input:
378201 949180 948990 948979 949231 949167 948915 948947 949284 949187 948945 949039 948922 949080 949020 949296 949143 949178 948878 949143 949334 949169 949096 949292 949057 949166 949368 949167 949316 949399 948884 949332 949150 949234 948882 949180 949201 948928 948926 949055 949247 949003 949225...
output:
24549909112
result:
ok 1 number(s): "24549909112"