QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#151656#6327. Count Arithmetic ProgressionForever_Young#WA 51ms5996kbC++142.7kb2023-08-27 13:10:052023-08-27 13:10:06

Judging History

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

  • [2023-08-27 13:10:06]
  • 评测
  • 测评结果:WA
  • 用时:51ms
  • 内存:5996kb
  • [2023-08-27 13:10:05]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
const int N = 300033;
typedef long long LL;
const int mod = 998244353;
constexpr LL fastpo(LL x, LL n, int mod) {
	LL res = 1;
	x %= mod;
	while(n) {
		if(n & 1) {
			res = res * x % mod;
		}
		x = x * x % mod;
		n /= 2;
	}
	
	return res;
}
struct P {
	LL x, y;
	P operator - (const P & b) const {
		return P{x - b.x, y - b.y};
	}
	LL operator * (const P & b) const {
		return x * b.y - y * b.x;
	}
	LL floor() const {
		assert(x > 0);
		return y >= 0 ? y / x : (y - (x - 1)) / x;
	}
	LL ceil() const {
		assert(x > 0);
		return y >= 0 ? (y + (x - 1)) / x : y / x;
	}
};
int l[N], r[N];
const LL inf = 1000000000000;
			//  123456789012
int main() {
	int n;
	scanf("%d", &n);
	vector<P> vec;
	for(int i = 1; i <= n; i++) {
		scanf("%d", &l[i]);
		P p = P{i, l[i]};
		while(vec.size() >= 2 && (p - vec.back()) * (vec.back() - vec[vec.size() - 2]) <= 0) {
			vec.pop_back();
		}
		vec.pb(p);
	}
	vector<pair<LL, P> > lb, ub;
	LL sl = -inf;
	for(int i = (int)vec.size() - 1; i >= 0; i--) {
		LL nxt;
		if(i == 0) {
			nxt = inf;
		}else {
			nxt = (vec[i] - vec[i - 1]).floor();
		}
		lb.pb({sl, vec[i]});
		sl = nxt + 1;
	}



	bool flag = true;
	vec.clear();
	for(int i = 1; i <= n; i++) {
		scanf("%d", &r[i]);
		P p = P{i, r[i]};
		while(vec.size() >= 2 && (p - vec.back()) * (vec.back() - vec[vec.size() - 2]) >= 0) {
			vec.pop_back();
		}
		vec.pb(p);
		
	}

	sl = -inf;
	for(int i = 0; i < (int)vec.size(); i++) {
		LL nxt;
		if(i == (int)vec.size() - 1) {
			nxt = inf;
		}else {
			nxt = (vec[i + 1] - vec[i]).floor();
		}
		ub.pb({sl, vec[i]});
		sl = nxt + 1;
	}


	int i = 0, j = 0;
	LL ans = 0, inv2 = fastpo(2, mod - 2, mod);
	while(i < lb.size() && j < ub.size()) {
		//cout << i << ' ' << j << endl;
		LL il = lb[i].fi;
		LL ir = i + 1 == lb.size() ? inf : lb[i + 1].fi - 1;
		
		LL jl = ub[j].fi;
		LL jr = j + 1 == ub.size() ? inf : ub[j + 1].fi - 1;

		if(ir < jl) {
			i++;
		}else if(jr < il) {
			j++;
		}else {
			LL le = max(il, jl);
			LL ri = min(ir, jr);
			P lv = lb[i].se;
			P uv = ub[j].se;
			if(lv.x < uv.x) {
				ri = min(ri, (uv - lv).floor());
			}else if(lv.x > uv.x) {
				le = max(le, (lv - uv).ceil());
			}
			if(le > ri) {
			}else {
				//le <= k <= ri, lv.y <= ? <= uv.y + (lv.x - uv.x) * k
				ans = ans + (ri - le + 1) % mod * ((uv.y + (lv.x - uv.x) * ri - lv.y + 1 + uv.y + (lv.x - uv.x) * le - lv.y + 1) % mod) % mod * inv2 % mod;
				ans %= mod;
			}
			if(ir < jr) {
				i++;	
			}else {
				j++;
			}
		}
	}
	cout << ans << endl;
}







Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3904kb

input:

3
5 5 2
7 6 7

output:

6

result:

ok 1 number(s): "6"

Test #2:

score: 0
Accepted
time: 1ms
memory: 3616kb

input:

4
2 3 1 6
5 6 4 8

output:

0

result:

ok 1 number(s): "0"

Test #3:

score: -100
Wrong Answer
time: 51ms
memory: 5996kb

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:

0

result:

wrong answer 1st numbers differ - expected: '2000014', found: '0'