QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#546583#8556. Somewhere Over the RainbowmengzddRE 0ms0kbC++141.9kb2024-09-04 09:53:182024-09-04 09:53:23

Judging History

你现在查看的是最新测评结果

  • [2024-09-04 09:53:23]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-09-04 09:53:18]
  • 提交

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

output:


result: