QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#97637#6327. Count Arithmetic ProgressionjeffqiWA 32ms19232kbC++142.4kb2023-04-17 18:14:212023-04-17 18:14:23

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-17 18:14:23]
  • 评测
  • 测评结果:WA
  • 用时:32ms
  • 内存:19232kb
  • [2023-04-17 18:14:21]
  • 提交

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)
#define grep(i,u) for (int i = head[u],v = e[i].v; i; v = e[i = e[i].nxt].v)
#define LL long long
#define pii pair<int,int>
#define pll pair<LL,LL>
#define fi first
#define se second
#define eb emplace_back
#define mp make_pair
using namespace std;
LL read() {
	LL  x = 0,y = 1; char ch = getchar(); while (!isdigit(ch)) {if (ch == '-') y = -y; ch = getchar();}
	while (isdigit(ch)) {x = x*10+ch-'0'; ch = getchar();} return x*y;
}
namespace qiqi {
	const LL N = 3e5+5,INF = 0x3f3f3f3f3f3f3f3f,P = 998244353; int n,m; LL la[N],ra[N],lb[N],rb[N];
	struct Pnt {
		LL x,y;
		Pnt friend operator - (Pnt a,Pnt b) {
			return (Pnt){a.x-b.x,a.y-b.y};
		}
		LL fslp() {
			LL a = x,b = y;
			if (a < 0) {
				a = -a; b = -b;
			}
			if (b >= 0) return b/a;
			return -((Pnt){a,-b}).cslp();
		}
		LL cslp() {
			LL a = x,b = y;
			if (a < 0) {
				a = -a; b = -b;
			}
			if (b >= 0) return (b+a-1)/a;
			return -((Pnt){a,-b}).fslp();
		}
	} a[N],b[N];
	LL cross(Pnt a,Pnt b) {
		return a.x*b.y-a.y*b.x;
	}
	LL s(LL l,LL r) {
		l %= P; r %= P;
		return (l+r)*(r-l+1)/2%P;
	}
	void main() {
		n = read(); int x = 0,y = 0;
		rep(i,1,n) {
			a[i] = (Pnt){i,read()};
		}
		rep(i,1,n) {
			b[n-i+1] = (Pnt){i,read()};
		}
		rep(i,1,n) {
			while (x > 1 && cross(a[x]-a[x-1],a[i]-a[x]) >= 0) --x;
			a[++x] = a[i];
		}
		rep(i,1,n) {
			while (y > 1 && cross(b[y]-b[y-1],b[i]-b[y]) >= 0) --y;
			b[++y] = b[i];
		}
		n = x; m = y;
		ra[1] = rb[1] = INF; la[n] = lb[m] = -INF;
		rep(i,2,n) {
			ra[i] = (a[i]-a[i-1]).fslp();
			la[i-1] = (a[i]-a[i-1]).cslp();
		}
		rep(i,2,m) {
			rb[i] = (b[i]-b[i-1]).fslp();
			lb[i-1] = (b[i]-b[i-1]).cslp();
		}
		LL ans = 0,lstr = INF;
		for (int i = 1,j = 1; i <= n && j <= m; la[i] > lb[j] ? ++i : ++j) {
			LL l = max(la[i],lb[j]),r = min(ra[i],rb[j]); Pnt k = b[j]-a[i];
			if (k.x < 0) {
				l = max(l,(b[j]-a[i]).cslp());
			}
			if (k.x > 0) {
				r = min(r,(b[j]-a[i]).fslp());
			}
			r = min(r,lstr-1);
			if (l > r) continue;
//			LL lst = ans;
			LL len = (r-l+1)%P;
			ans = (ans+(k.y+1%P)*len%P-k.x%P*s(l,r)%P)%P;
//			printf("%d %d %lld %lld %lld %lld %lld\n",i,j,l,r,k.x,k.y,ans-lst);
			lstr = r;
		}
		printf("%lld\n",(ans+P)%P);
	}
}
int main() {
	qiqi::main(); return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 13720kb

input:

3
5 5 2
7 6 7

output:

6

result:

ok 1 number(s): "6"

Test #2:

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

input:

4
2 3 1 6
5 6 4 8

output:

0

result:

ok 1 number(s): "0"

Test #3:

score: 0
Accepted
time: 32ms
memory: 19232kb

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: 13768kb

input:

2
1 1
1000000000000 1000000000000

output:

471979365

result:

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