QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#905723 | #1465. Not Our Problem | dieselhuang | AC ✓ | 44ms | 32100kb | C++14 | 2.1kb | 2025-02-19 15:01:39 | 2025-02-19 15:02:10 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
namespace IO{
static char buf[1000000],*p1=buf,*p2=buf;
#define GC() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++)
ll read(){
ll x = 0; bool fl = false; char c = GC();
while(c < '0' || c > '9'){
if(c == '-') fl = true;
c = GC();
}
while(c >= '0' && c <= '9'){
x = (x << 3) + (x << 1) + c - '0'; c = GC();
}
return fl ? -x : x;
}
}
using namespace IO;
const int mxn = 1e6+10, mxB = 1e6+10, mxm = 1e9, mod = 998244353;
const ll inf = 1e18;
int n, ans = 1, s[mxB];
ll k, B, a[mxn], b[mxn], f[mxB];
int mysqrt(ll x){
int l = 0, r = min(x, (ll)mxm), md;
while(l < r){
md = l + r + 1 >> 1;
if((ll)md * md <= x) l = md;
else r = md - 1;
}
return l;
}
ll calc(ll x, ll y){
int res = (x + y + 1) % mod;
int l, r, rr = min(B, x), md;
l = 0; r = rr;
while(l < r){
md = l + r + 1 >> 1;
if(y <= f[md]) l = md;
else r = md - 1;
}
res = (res + l * y + s[rr] + mod - s[l]) % mod;
if(x <= B) return res;
l = 0; r = rr = min(B, y);
while(l < r){
md = l + r + 1 >> 1;
if(x <= f[md]) l = md;
else r = md - 1;
}
res = (res + l * x + s[rr] + mod - s[l] + mod - rr * B % mod) % mod;
return res;
}
int main()
{
int i;
n = read(); k = read();
B = 0;
while(B * B * B <= k) B++;
B--;
for(i = 1, f[0] = s[0] = 0; i <= B; i++){
f[i] = k / i / i;
s[i] = (s[i - 1] + f[i]) % mod;
}
for(i = 1; i <= n; i++){
a[i] = read();
}
a[0] = a[n + 1] = 0;
for(i = 0; i <= n + 1; i++){
if(a[i] > 0){
b[i] = (a[i] <= B ? k / a[i] / a[i] : mysqrt(k / a[i]));
}else b[i] = inf;
}
for(i = 1; i < n; i++){
if(a[i] > b[i + 1]){ printf("0"); return 0; }
}
for(i = 1; i <= n; i++){
if(a[i] < 0 && a[i - 1] <= 0 && a[i + 1] <= 0){ printf("-1"); return 0; }
}
for(i = 1; i <= n; i++){
if(a[i] >= 0) continue;
if(a[i + 1] < 0){
ans = ans * calc(b[i - 1], b[i + 2]) % mod;
i++;
}else{
ans = (min(b[i - 1], b[i + 1]) + 1) % mod * ans % mod;
}
}
printf("%d", ans);
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 9928kb
input:
4 100 -1 7 2 -1
output:
104
result:
ok 1 number(s): "104"
Test #2:
score: 0
Accepted
time: 0ms
memory: 11972kb
input:
4 100 10 -1 -1 1
output:
240
result:
ok 1 number(s): "240"
Test #3:
score: 0
Accepted
time: 0ms
memory: 9936kb
input:
1 0 -1
output:
-1
result:
ok 1 number(s): "-1"
Test #4:
score: 0
Accepted
time: 0ms
memory: 9640kb
input:
2 10 10 10
output:
0
result:
ok 1 number(s): "0"
Test #5:
score: 0
Accepted
time: 0ms
memory: 9932kb
input:
7 1000 -1 25 0 388 -1 -1 1
output:
14014
result:
ok 1 number(s): "14014"
Test #6:
score: 0
Accepted
time: 0ms
memory: 10060kb
input:
10 1000000 -1 71350 0 6 -1 2 2 -1 -1 358968
output:
652782809
result:
ok 1 number(s): "652782809"
Test #7:
score: 0
Accepted
time: 6ms
memory: 18840kb
input:
7 1000000000000000000 -1 193562447565998153 0 10833 -1 -1 12700
output:
429385005
result:
ok 1 number(s): "429385005"
Test #8:
score: 0
Accepted
time: 0ms
memory: 11976kb
input:
100 1000 -1 174 2 -1 -1 1 2 -1 -1 2 139 -1 -1 1 4 -1 -1 1 1 -1 -1 4 18 -1 -1 356 1 -1 -1 31 1 -1 -1 1 2 -1 -1 1 7 -1 -1 2 0 509 -1 -1 174 0 22 -1 -1 1 1 -1 -1 801 0 2 -1 -1 6 2 -1 -1 1 23 -1 -1 446 0 927 -1 -1 635 1 -1 -1 513 0 5 -1 -1 2 6 -1 -1 2 1 -1 -1 839 0 342 -1 -1 8 1 -1 -1 2
output:
240069117
result:
ok 1 number(s): "240069117"
Test #9:
score: 0
Accepted
time: 0ms
memory: 11980kb
input:
100 1000000 2 -1 -1 257208 1 -1 -1 80 14 -1 -1 20 113 -1 -1 2 155991 -1 -1 1 805463 -1 -1 734 1 -1 -1 942182 0 3 -1 -1 1 1 -1 -1 3 88674 -1 -1 718 0 793 -1 -1 540 1 -1 -1 1 893042 -1 -1 891 0 491 -1 -1 6 18 -1 -1 1 735332 -1 -1 1 1 -1 -1 231702 0 22 -1 -1 1 476 -1 -1 826 20 -1 -1 1 29 -1 -1 2 989 -1...
output:
279593366
result:
ok 1 number(s): "279593366"
Test #10:
score: 0
Accepted
time: 6ms
memory: 21408kb
input:
97 1000000000000000000 -1 55 1 -1 -1 844479880 0 123881535849416001 -1 -1 128083297778537531 1 -1 -1 171572811 0 352900396625380054 -1 -1 1 1 -1 -1 41 6 -1 -1 21627 155 -1 643122694 0 392322295 -1 -1 254987357 2 -1 -1 4 0 571457328786259212 -1 -1 1 8816 -1 -1 131254846109630352 0 971779784498766346 ...
output:
188490398
result:
ok 1 number(s): "188490398"
Test #11:
score: 0
Accepted
time: 23ms
memory: 23196kb
input:
999998 1000 -1 343 1 -1 -1 1 3 -1 -1 1 1 -1 -1 2 0 468 -1 -1 1 1 -1 -1 783 0 5 -1 -1 2 0 760 -1 -1 318 1 -1 -1 1 320 -1 -1 27 1 -1 -1 2 2 -1 -1 2 1 -1 -1 997 1 -1 -1 547 0 313 -1 -1 4 0 304 -1 -1 1 4 -1 -1 980 0 96 -1 -1 1 797 -1 -1 13 0 13 -1 -1 19 0 401 -1 -1 1 1 -1 -1 5 5 -1 -1 26 0 458 -1 -1 6 0...
output:
104236068
result:
ok 1 number(s): "104236068"
Test #12:
score: 0
Accepted
time: 26ms
memory: 23196kb
input:
999998 1000000 -1 538406 1 -1 -1 1 2 -1 -1 288 0 393 -1 -1 256582 0 111893 -1 1 1 -1 -1 105454 0 40 -1 -1 1 4 -1 -1 6 1 -1 -1 3 0 588226 -1 -1 2 22 -1 -1 1 477043 -1 -1 2 912 -1 -1 3 0 539669 -1 -1 1 1 -1 -1 597 0 423 -1 -1 717193 0 506800 -1 -1 424362 0 523732 -1 -1 411789 0 2 -1 -1 2 0 681371 -1 -...
output:
945384981
result:
ok 1 number(s): "945384981"
Test #13:
score: 0
Accepted
time: 44ms
memory: 32100kb
input:
999999 1000000000000000000 34 -1 -1 10403 0 945252394656439232 -1 -1 11 3 -1 -1 2789 153814328 -1 -1 685484514683924741 1 -1 -1 1 14600 -1 -1 162108378 0 942407706831037158 -1 -1 1 81 -1 -1 286801961 1 -1 -1 13177 356030442 -1 -1 9557 0 647686052355282463 -1 -1 797322887 0 33989350 -1 -1 31337243480...
output:
727350500
result:
ok 1 number(s): "727350500"
Test #14:
score: 0
Accepted
time: 0ms
memory: 11844kb
input:
50 1000 -1 -1 -1 694 26 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 555 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
output:
0
result:
ok 1 number(s): "0"
Test #15:
score: 0
Accepted
time: 13ms
memory: 31976kb
input:
1000000 1000000000000000000 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1...
output:
-1
result:
ok 1 number(s): "-1"
Test #16:
score: 0
Accepted
time: 1ms
memory: 9804kb
input:
50 1000 210 -1 -1 -1 -1 -1 836 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 517 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 31 -1 128 -1 -1 -1 -1
output:
0
result:
ok 1 number(s): "0"
Test #17:
score: 0
Accepted
time: 11ms
memory: 31976kb
input:
1000000 1000000000000000000 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1...
output:
0
result:
ok 1 number(s): "0"
Test #18:
score: 0
Accepted
time: 0ms
memory: 9936kb
input:
7 100 -1 101 0 1 -1 -1 40
output:
202
result:
ok 1 number(s): "202"
Test #19:
score: 0
Accepted
time: 0ms
memory: 9932kb
input:
17 20 2 -1 -1 2 3 -1 -1 1 3 -1 -1 21 0 5 -1 -1 1
output:
186624
result:
ok 1 number(s): "186624"
Test #20:
score: 0
Accepted
time: 1ms
memory: 10008kb
input:
8 1000000000000 5 -1 -1 2 1 -1 -1 2
output:
667440443
result:
ok 1 number(s): "667440443"
Test #21:
score: 0
Accepted
time: 1ms
memory: 12048kb
input:
4 1000000000000 5 -1 -1 2
output:
709877272
result:
ok 1 number(s): "709877272"
Test #22:
score: 0
Accepted
time: 0ms
memory: 10004kb
input:
4 1000000000000 1 -1 -1 2
output:
232569899
result:
ok 1 number(s): "232569899"