QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#108817 | #6327. Count Arithmetic Progression | 8BQube# | RE | 3ms | 5480kb | C++14 | 2.7kb | 2023-05-26 18:12:57 | 2023-05-26 18:13:02 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define X first
#define Y second
#define ALL(v) v.begin(), v.end()
#define pb push_back
#define SZ(a) ((int)a.size())
const ll MOD = 998244353;
const ll TWO = (MOD + 1) / 2;
const ll INF = 1e13;
ll floor(ll a, ll b) {
return a / b - (a % b && ((a < 0) ^ (b < 0)));
}
ll ceil(ll a, ll b) {
return a / b + (a % b && ((a < 0) ^ (b > 0)));
}
ll lft[300005], rgt[300005];
void add(ll &x, ll val) {
x = (x + val) % MOD;
}
ll get_sum(ll l, ll r) {
l %= MOD;
r %= MOD;
return (l + r) * (r + MOD - l + 1) % MOD * TWO % MOD;
}
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int n;
ll ans = 0;
cin >> n;
for (int i = 1; i <= n; ++i)
cin >> lft[i];
for (int i = 1; i <= n; ++i)
cin >> rgt[i];
vector<pll> fL, fR;
for (int i = 1; i <= n; ++i) {
while (SZ(fL) >= 2 && fL.back().Y >= ceil(lft[fL[SZ(fL) - 2].X] - lft[i], i - fL[SZ(fL) - 2].X))
fL.pop_back();
if (fL.empty()) fL.pb(pll(i, -INF));
else fL.pb(pll(i, ceil(lft[fL.back().X] - lft[i], i - fL.back().X)));
}
for (int i = n; i >= 1; --i) {
while (SZ(fR) >= 2 && fR.back().Y >= ceil(rgt[i] - rgt[fR[SZ(fR) - 2].X], fR[SZ(fR) - 2].X - i))
fR.pop_back();
if (fR.empty()) fR.pb(pll(i, -INF));
else fR.pb(pll(i, ceil(rgt[i] - rgt[fR.back().X], fR.back().X - i)));
}
ll nw = -INF;
int flag = 0;
for (int i = 0, j = 0; i < SZ(fL) && j < SZ(fR);) {
while (i + 1 < SZ(fL) && nw >= fL[i + 1].Y) ++i;
while (j + 1 < SZ(fR) && nw >= fR[j + 1].Y) ++j;
ll Lnxt, Rnxt;
if (i + 1 < SZ(fL)) Lnxt = fL[i + 1].Y;
else Lnxt = INF;
if (j + 1 < SZ(fR)) Rnxt = fR[j + 1].Y;
else Rnxt = INF;
ll nxt = min(Lnxt, Rnxt) - 1;
auto cal = [&]() {
if (nw > nxt) return;
add(ans, nxt - nw + 1);
add(ans, (nxt - nw + 1) % MOD * (rgt[fR[j].X] % MOD));
add(ans, fR[j].X * get_sum(nw, nxt));
add(ans, MOD - (nxt - nw + 1) % MOD * (lft[fL[i].X] % MOD) % MOD);
add(ans, MOD - fL[i].X * get_sum(nw, nxt) % MOD);
};
if (nxt * fL[i].X + lft[fL[i].X] <= nxt * fR[j].X + rgt[fR[j].X]) {
if (!flag) {
nw = ceil(rgt[fR[j].X] - lft[fL[i].X], fL[i].X - fR[j].X);
flag = 1;
}
cal();
}
else if (flag) {
nxt = floor(rgt[fR[j].X] - lft[fL[i].X], fL[i].X - fR[j].X);
cal();
break;
}
nw = nxt + 1;
if (i + 1 == SZ(fL) && j + 1 == SZ(fR)) break;
}
cout << ans << "\n";
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 5392kb
input:
3 5 5 2 7 6 7
output:
6
result:
ok 1 number(s): "6"
Test #2:
score: 0
Accepted
time: 2ms
memory: 5480kb
input:
4 2 3 1 6 5 6 4 8
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: -100
Runtime Error
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 ...