QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#151656 | #6327. Count Arithmetic Progression | Forever_Young# | WA | 51ms | 5996kb | C++14 | 2.7kb | 2023-08-27 13:10:05 | 2023-08-27 13:10:06 |
Judging History
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'