QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #558765 | #8556. Somewhere Over the Rainbow | lmh_qwq | WA | 1ms | 5740kb | C++14 | 1.3kb | 2024-09-11 18:26:52 | 2024-09-11 18:26:57 |
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;
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;
k=(k+MOD)%MOD;
(ans+=(k+1)%MOD*p1%MOD*(p1+1)%MOD*inv2)%=MOD;
(ans+=k%MOD*p2%MOD*(p2+1)%MOD*inv2)%=MOD;
(ans+=(k+1)%MOD*p1%MOD*p2)%=MOD;
}
cout<<(ans+MOD)%MOD<<endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5652kb
input:
3 6 1 100 4 42 5 22
output:
310
result:
ok 1 number(s): "310"
Test #2:
score: 0
Accepted
time: 0ms
memory: 5740kb
input:
0 5
output:
10
result:
ok 1 number(s): "10"
Test #3:
score: 0
Accepted
time: 1ms
memory: 5548kb
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: 5740kb
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: 5732kb
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'