QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#463355#6327. Count Arithmetic ProgressionZSH_ZSHWA 61ms21124kbC++142.2kb2024-07-04 18:59:142024-07-04 18:59:14

Judging History

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

  • [2024-07-04 18:59:14]
  • 评测
  • 测评结果:WA
  • 用时:61ms
  • 内存:21124kb
  • [2024-07-04 18:59:14]
  • 提交

answer

#include<bits/stdc++.h>
#define rep(i,a,b) for (int i=(a);i<=(b);i++)
#define drep(i,a,b) for (int i=(a);i>=(b);i--)
using namespace std;
typedef long long ll;

#define fir first
#define sec second
const ll inf=1e18;

const int mod=998244353;
const int inv2=(mod+1)/2;
inline ll norm(ll x)
{
	x%=mod;
	x+=mod;
	x%=mod;
	return x;
}

struct Line
{
	ll k,b;
	ll eval(ll x)
	{
		return k*x+b;
	}
	ll query(int l,int r)
	{
		ll x=eval(l);
		ll y=eval(r);
		return norm((x+y)%mod*(r-l+1)%mod*inv2%mod);
	}
};

struct info
{
	vector<Line> a;
	void build(vector<Line> b)
	{
		sort(b.begin(),b.end(),[&](auto x,auto y){return x.k>y.k;});
		a.clear();

		for (auto x:b)
		{
			while (a.size()>=2)
			{
				auto y=a.back();
				auto z=a[a.size()-2];

				ll c=(x.b-z.b)*(z.k-y.k)-(y.b-z.b)*(z.k-x.k);
				if (c<=0) a.pop_back();
				else break;
			}
			a.push_back(x);
		}
	}
	pair<ll,int> eval(ll x) // qmin
	{
		int l=0,r=a.size()-1;
		while (l<r)
		{
			int mid=(l+r)>>1;
			if (a[mid].eval(x)<a[mid+1].eval(x)) r=mid;
			else l=mid+1;
		}
		return {a[l].eval(x),l};
	}

	ll query(ll l,ll r)
	{
		assert(l<=r);
		auto x=eval(l),y=eval(r);
		if (x.sec==y.sec) return a[x.sec].query(l,r);
		ll mid=(l+r)>>1;
		return norm(query(l,mid)+query(mid+1,r));
	}
};

int main()
{
	ios::sync_with_stdio(false); cin.tie(0);

	int n; cin>>n;
	vector<ll> L(n),R(n);
	rep(i,0,n-1) cin>>L[i];
	rep(i,0,n-1) cin>>R[i];

	info up,dn;
	{
		vector<Line> x;
		rep(i,0,n-1) x.push_back({-i,R[i]});
		up.build(x);
	}
	{
		vector<Line> x;
		rep(i,0,n-1) x.push_back({i,-L[i]+1});
		dn.build(x);
	}

	auto f=[&](ll x)
	{
		return up.eval(x).fir+dn.eval(x).fir;
	};
	ll p=0;
	{
		ll l=-3e12,r=3e12;
		while (r-l>20)
		{
			ll m1=(l+l+r)/3,m2=(l+r+r)/3;
			if (f(m1)>f(m2)) r=m2;
			else l=m1;
		}
		ll v=-inf;
		for (ll i=l;i<=r;i++)
		{
			ll w=f(i);
			if (w>v)
			{
				p=i;
				v=w;
			}
		}
	}
	if (f(p)<=0)
	{
		printf("0\n");
		return 0;
	}

	ll x=p,y=p;
	drep(i,40,0)
	{
		ll d=(1ll<<i);
		if (f(x-d)>=0) x-=d;
		if (f(y+d)>=0) y+=d;
	}
	printf("%lld\n",norm(up.query(x,y)+dn.query(x,y)));

	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3732kb

input:

3
5 5 2
7 6 7

output:

6

result:

ok 1 number(s): "6"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3648kb

input:

4
2 3 1 6
5 6 4 8

output:

0

result:

ok 1 number(s): "0"

Test #3:

score: 0
Accepted
time: 61ms
memory: 21124kb

input:

300000
121398540794 60081434790 252920491076 43666218735 95583832019 21178121624 315727133812 89837170656 138389231466 174687947367 124350262341 108583578309 289629745492 321006985392 301201031648 138149017169 255983300245 138801256482 285614769875 130583757928 261690466826 74624776159 303504239011 ...

output:

2000014

result:

ok 1 number(s): "2000014"

Test #4:

score: -100
Wrong Answer
time: 0ms
memory: 3792kb

input:

2
1 1
1000000000000 1000000000000

output:

42808130

result:

wrong answer 1st numbers differ - expected: '276262510', found: '42808130'