QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#553842 | #8556. Somewhere Over the Rainbow | Purslane | WA | 1ms | 5604kb | C++14 | 1019b | 2024-09-08 21:10:51 | 2024-09-08 21:10:53 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=2e5+10;
int n,m,x[MAXN],y[MAXN];
__int128 sum;
struct INFO {int x,y,k;__int128 sum;};
stack<INFO> st;
void insert(int X,int Y) {
while(!st.empty()) {
__int128 x=st.top().x,y=st.top().y,k=st.top().k;
__int128 Ymx=y+(X-x)*k-(X-x)*(X-x+1)/2;
if(Ymx<Y) {st.pop();continue ;}
__int128 dt=Ymx-Y,del=dt/(X-x),d=X-x;
__int128 sum=y*d+k*d+k*d*d-(k+d+1)*d*(d+1)/2+d*(d+1)*(d+d+1)/6;
sum-=del*(d*(d+1)/2),k-=del;
k-=d;
if(dt%d) dt%=d,sum-=d*(d+1)/2,k--;
st.push({X,Y,k,sum});
break ;
}
return ;
}
signed main() {
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>m;
ffor(i,1,n) cin>>x[i]>>y[i];
st.push({0,0,(__int128)100000000000000000000,0});
ffor(i,1,n) insert(x[i],y[i]);
insert(m,0);
while(!st.empty()) sum+=st.top().sum,st.pop();
cout<<(int)(sum%998244353);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5604kb
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: 3620kb
input:
0 5
output:
10
result:
ok 1 number(s): "10"
Test #3:
score: -100
Wrong Answer
time: 0ms
memory: 3828kb
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:
9775
result:
wrong answer 1st numbers differ - expected: '10725', found: '9775'