QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#97637 | #6327. Count Arithmetic Progression | jeffqi | WA | 32ms | 19232kb | C++14 | 2.4kb | 2023-04-17 18:14:21 | 2023-04-17 18:14:23 |
Judging History
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;
}
详细
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'