QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#546583 | #8556. Somewhere Over the Rainbow | mengzdd | RE | 0ms | 0kb | C++14 | 1.9kb | 2024-09-04 09:53:18 | 2024-09-04 09:53:23 |
answer
#include <bits/stdc++.h>
#define FOR(i,j,k) for(int i=j;i<=k;++i)
#define NFOR(i,j,k) for(int i=j;i>=k;--i)
#define mkp make_pair
#define fst first
#define sec second
#define inl inline
using namespace std;
typedef long long ll;
typedef __int128 lll;
typedef unsigned int ui;
typedef pair< ll,ll > pll;
const int N=2e5+5,mod=998244353;
inline ll read()
{
ll s=0,w=1; char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') w=-1; ch=getchar();}
while(ch>='0'&&ch<='9') {s=(s<<1)+(s<<3)+ch-'0',ch=getchar();}
return s*w;
}
void file()
{
freopen("data.out","r",stdin);
freopen("ans2.out","w",stdout);
}
void teltim(int x)
{
clock_t c1=0;
if(x) c1=clock();
else cerr<<endl<<clock()-c1<<"ms"<<endl;
}
int n;
ll m;
pll p[N];
ll divflr(ll a,ll b) // б\xc2\xca\xcf\xc2ȡ\xd5\xfb
{
return a/b-(((a^b)<0&&a%b!=0)?1:0);
}
ll divcel(ll a,ll b) // б\xc2\xca\xc9\xcfȡ\xd5\xfb
{
return a/b+(((a^b)>0&&a%b!=0)?1:0);
}
ll cal(ll a,ll b,ll c)
{
ll ret=0;
a%=mod;
ret=(ret+((lll)a*b)%mod)%mod;
ret=(ret+((lll)c*(((lll)a*(a-1))>>1)%mod)%mod)%mod;
return ret%mod;
}
int main()
{
file();
n=read(),m=read();
FOR(i,1,n) p[i].fst=read(),p[i].sec=read();
p[0]=mkp(0ll,0ll);p[n+1]=mkp(m,0ll);
FOR(i,0,n+1)
{
ll x=p[i].fst;
p[i].sec+=(((x-1)*x)>>1);
}
vector <pll> sto;
FOR(i,0,n+1)
{
for(;sto.size()>=2;sto.pop_back())
{
const pll a=sto.end()[-2];
const pll b=sto.end()[-1];
const pll c=p[i];
if(divflr(b.sec-a.sec,b.fst-a.fst)>=divcel(c.sec-b.sec,c.fst-b.fst)) break;
}
sto.push_back(p[i]);
}
ll ans=0;
for(ui i=0;i<sto.size()-1;++i)
{
const pll &p0=sto[i],&p1=sto[i+1];
const ll dx=p1.fst-p0.fst;
const ll dy=p1.sec-p0.sec;
const ll q=divflr(dy,dx);
const ll r=dy-dx*q;
ans=(ans+cal(r,p0.sec,q+1))%mod;
ans=(ans+cal(dx-r,p0.sec+r*(q+1),q))%mod;
}
lll divi=(((lll)m*(m-1)*(m-2))/6)%mod;
//printf("%lld\n",(ll)divi);
ans=(ans-(ll)divi+mod)%mod;
printf("%lld",ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Dangerous Syscalls
input:
3 6 1 100 4 42 5 22