QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #558773 | #8556. Somewhere Over the Rainbow | lmh_qwq | WA | 1ms | 5700kb | C++14 | 1.4kb | 2024-09-11 18:29:09 | 2024-09-11 18:29:10 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=200007,MOD=998244353,inv2=499122177,inv3=332748118;
struct limit{ll id,x;}a[N];
ll n,m,ans,ok[N],stk[N],top;
pair<ll,ll> b[N];
int main(){
cin>>n>>m;
for (int i=1;i<=n;++i){
cin>>a[i].id>>a[i].x;
a[i].x+=a[i].id*(a[i].id-1)/2;
}
a[++n]=(limit){m,m*(m-1)/2};
a[0]=(limit){0,0};
ans=m%MOD*(m-1)%MOD*(m+1)%MOD*inv2%MOD*inv3%MOD*(MOD-1)%MOD;
for (int i=1;i<=n;++i){
ll dx=a[i].id-a[i-1].id,dy=a[i].x-a[i-1].x;
ll k=dy/dx;
while(k*dx>dy) --k;
while((k+1)*dx<dy) ++k;
if (k*dx==dy) b[i]=make_pair(k,k);
else b[i]=make_pair(k,k+1);
while(top&&b[top].second<b[i].first) --top;
stk[++top]=i;
}
for (int i=1;i<=top;++i){
ll pre=stk[i-1],now=stk[i];
(ans+=a[pre].x%MOD*(a[now].id-a[pre].id)%MOD)%=MOD;
ll dx=a[now].id-a[pre].id,dy=a[now].x-a[pre].x;
ll k=dy/dx;
while(k*dx>dy) --k;
while((k+1)*dx<dy) ++k;
ll p1=dy-k*dx;ll p2=dx-p1;
assert(p1*(k+1)+p2*k==dy);
assert(p1>=0&&p2>=0);
k=(k%MOD+MOD)%MOD;
(ans+=(k+1)%MOD*p1%MOD*(p1+1)%MOD*inv2%MOD)%=MOD;
(ans+=k%MOD*p2%MOD*(p2+1)%MOD*inv2%MOD)%=MOD;
(ans+=(k+1)%MOD*p1%MOD*p2%MOD)%=MOD;
}
cout<<(ans+MOD)%MOD<<endl;
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 5688kb
input:
3 6 1 100 4 42 5 22
output:
310
result:
ok 1 number(s): "310"
Test #2:
score: 0
Accepted
time: 1ms
memory: 5620kb
input:
0 5
output:
10
result:
ok 1 number(s): "10"
Test #3:
score: 0
Accepted
time: 1ms
memory: 5700kb
input:
20 50 4 11 7 4 8 20 13 9 14 29 15 26 16 19 18 18 29 46 30 7 34 37 35 16 38 14 39 47 40 18 42 30 43 6 44 23 47 13 48 4
output:
10725
result:
ok 1 number(s): "10725"
Test #4:
score: 0
Accepted
time: 1ms
memory: 5680kb
input:
40 100 3 20 4 67 5 62 7 75 9 49 11 14 14 31 18 11 19 5 24 98 25 100 28 35 30 19 31 20 32 71 37 29 38 5 40 94 45 95 46 65 51 2 52 52 53 61 54 77 57 50 59 69 61 30 65 50 67 4 68 56 73 99 75 15 76 47 78 52 79 72 83 91 88 44 89 3 91 55 94 2
output:
84575
result:
ok 1 number(s): "84575"
Test #5:
score: -100
Wrong Answer
time: 1ms
memory: 5680kb
input:
60 150 1 119 4 135 5 75 9 13 11 72 15 34 17 130 21 12 26 107 30 133 33 18 34 135 36 78 37 95 38 26 42 24 44 25 51 49 52 73 54 40 55 100 56 67 61 128 62 87 74 131 75 103 77 84 78 37 81 51 82 83 83 89 84 58 89 117 93 148 94 127 95 118 96 103 97 49 98 28 99 83 102 65 105 97 107 103 109 9 113 40 116 107...
output:
284050
result:
wrong answer 1st numbers differ - expected: '286360', found: '284050'