QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#103041 | #6327. Count Arithmetic Progression | Alpha_Q# | WA | 71ms | 8132kb | C++17 | 3.3kb | 2023-05-04 05:18:21 | 2023-05-04 05:18:23 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 300010;
const ll INF = 1e17 + 69;
const int MOD = 998244353;
const ll INV_2 = 1 + MOD >> 1;
int n;
ll l[N], r[N];
inline bool bad (pair <ll, ll> A, pair <ll, ll> B, pair <ll, ll> C) {
return (__int128) (A.second - C.second) * (B.first - A.first) <= (__int128) (A.second - B.second) * (C.first - A.first);
}
inline ll floor (ll x, ll y) {
if (x % y == 0) return x / y;
return x < 0 ? x / y - 1 : x / y;
}
inline ll ceiling (ll x, ll y) {
if (x % y == 0) return x / y;
return x > 0 ? x / y + 1 : x / y;
}
inline ll range (ll l, ll r) {
if (l >= r) return 0;
ll gap = (r - l) % MOD * INV_2 % MOD, ret = (l + r - 1) % MOD * gap % MOD;
return ret < 0 ? ret + MOD : ret;
}
int main() {
cin >> n;
for (int i = 1; i <= n; ++i) scanf("%lld", l + i);
for (int i = 1; i <= n; ++i) scanf("%lld", r + i);
vector <array <ll, 3>> L, R;
vector <ll> events({-INF, INF});
{
vector <pair <ll, ll>> vec;
for (int i = n; i >= 1; --i) {
pair <ll, ll> cur(1 - i, l[i]);
while (vec.size() >= 2 and bad(vec[vec.size() - 2], vec.back(), cur)) vec.pop_back();
vec.emplace_back(cur);
}
ll last = -INF;
for (int i = 0; i < vec.size(); ++i) {
if (i + 1 == vec.size()) {
L.push_back({INF, vec[i].first, vec[i].second});
break;
}
ll at = ceiling(vec[i].second - vec[i + 1].second, vec[i + 1].first - vec[i].first);
L.push_back({at, vec[i].first, vec[i].second}), events.emplace_back(at), last = at;
}
}
{
vector <pair <ll, ll>> vec;
for (int i = 1; i <= n; ++i) {
pair <ll, ll> cur(i - 1, -r[i]);
while (vec.size() >= 2 and bad(vec[vec.size() - 2], vec.back(), cur)) vec.pop_back();
vec.emplace_back(cur);
}
ll last = -INF;
for (int i = 0; i < vec.size(); ++i) {
if (i + 1 == vec.size()) {
R.push_back({INF, vec[i].first, vec[i].second});
break;
}
ll at = ceiling(vec[i].second - vec[i + 1].second, vec[i + 1].first - vec[i].first);
R.push_back({at, vec[i].first, vec[i].second}), events.emplace_back(at), last = at;
}
}
sort(events.begin(), events.end());
events.erase(unique(events.begin(), events.end()), events.end());
ll ans = 0;
int L_at = 0, R_at = 0;
for (int i = 0; i + 1 < events.size(); ++i) {
ll inc = events[i], exc = events[i + 1];
if (L[L_at][0] == inc) ++L_at;
if (R[R_at][0] == inc) ++R_at;
ll l_a = L[L_at][1], l_b = L[L_at][2];
ll r_a = -R[R_at][1], r_b = -R[R_at][2];
if (l_a == r_a) {
if (l_b > r_b) continue;
ll gap = (exc - inc) % MOD, cur = (r_b - l_b + 1) % MOD * gap;
ans += cur, ans %= MOD;
} else {
if (l_a < r_a) {
ll lo = min(exc, max(inc, ceiling(l_b - r_b, r_a - l_a)));
ll gap = exc - lo, cur = (r_b - l_b + 1) % MOD * gap % MOD + (r_a - l_a) * range(lo, exc) % MOD;
ans += cur, ans %= MOD;
} else {
ll hi = max(inc, min(exc, floor(r_b - l_b, l_a - r_a) + 1));
ll gap = hi - inc, cur = (r_b - l_b + 1) % MOD * gap % MOD + (r_a - l_a) * range(inc, hi) % MOD;
ans += cur, ans %= MOD;
}
}
}
ans += MOD, ans %= MOD;
cout << ans << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 5664kb
input:
3 5 5 2 7 6 7
output:
6
result:
ok 1 number(s): "6"
Test #2:
score: 0
Accepted
time: 0ms
memory: 5564kb
input:
4 2 3 1 6 5 6 4 8
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: 0
Accepted
time: 71ms
memory: 8132kb
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: 2ms
memory: 5556kb
input:
2 1 1 1000000000000 1000000000000
output:
712821071
result:
wrong answer 1st numbers differ - expected: '276262510', found: '712821071'