QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#97695 | #6327. Count Arithmetic Progression | yzc2005 | WA | 58ms | 8052kb | C++14 | 2.8kb | 2023-04-17 22:42:38 | 2023-04-17 22:42:40 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
using i64 = long long;
using i128 = i64;
using pii = pair<i64, i64>;
#define rep(i, a, b) for (int i = a, I = b; i <= I; ++i)
#define per(i, a, b) for (int i = a, I = b; i >= I; --i)
template<typename T> void up(T &x, T y) { if (x < y) x = y; }
template<typename T> void down(T &x, T y) { if (x > y) x = y; }
const int N = 300005;
const i64 inf = 1'000'000'000'000;
int n;
i64 L[N], R[N];
i128 ans;
void operator-=(pii &A, const pii &B) {
A.first -= B.first;
A.second -= B.second;
}
bool anticlock(const pii &A, pii B, pii C) {
B -= A, C -= A;
return B.first * C.second >= C.first * B.second;
}
i64 eval(const pii &A, i64 x) {
return -A.first * x + A.second;
}
vector<pii> construct(i64 *A, bool type) {
vector<pii> stk;
rep(i, 0, n - 1) {
pii cur(i, A[i]);
while ((int) stk.size() > 1 && anticlock(stk[(int) stk.size() - 2], stk.back(), cur) == type) stk.pop_back();
stk.push_back(cur);
}
return stk;
}
int main() {
ios::sync_with_stdio(0), cin.tie(0);
cin >> n;
rep(i, 0, n - 1) cin >> L[i];
rep(i, 0, n - 1) cin >> R[i];
auto HL = construct(L, true);
auto HR = construct(R, false);
vector<i64> pts;
pts.push_back(-inf), pts.push_back(inf);
rep(i, 0, (int) HL.size() - 2) {
i64 pos = (HL[i + 1].second - HL[i].second) / (HL[i + 1].first - HL[i].first);
rep(t, -1, 1) pts.push_back(pos + t);
}
rep(i, 0, (int) HR.size() - 2) {
i64 pos = (HR[i + 1].second - HR[i].second) / (HR[i + 1].first - HR[i].first);
rep(t, -1, 1) pts.push_back(pos + t);
}
sort(pts.begin(), pts.end());
pts.resize(unique(pts.begin(), pts.end()) - pts.begin());
int pl = (int) HL.size() - 1, pr = 0;
rep(i, 0, (int) pts.size() - 2) {
i64 l = pts[i], r = pts[i + 1] - 1;
while (pl > 0 && eval(HL[pl - 1], l) > eval(HL[pl], l)) --pl;
while (pr + 1 < (int) HR.size() && eval(HR[pr + 1], l) < eval(HR[pr], l)) ++pr;
i128 vl = eval(HR[pr], l) - eval(HL[pl], l) + 1;
i128 vr = eval(HR[pr], r) - eval(HL[pl], r) + 1;
i128 diff = HL[pl].first - HR[pr].first;
assert(vr == vl + diff * (r - l));
if (diff > 0) {
swap(vl, vr);
diff = -diff;
}
assert(vl >= vr);
if (vl <= 0) continue;
// cerr << "? " << l << " " << r << " " << HL[pl].first << " " << HR[pr].first << "\n";
i128 len = r - l + 1;
if (vr < 0) down(len, vl / (-diff));
ans += vl * len + diff * len * (len - 1) / 2;
// cerr << int(vl) << " " << int(vr) << " " << int(ans) << "\n";
}
int ANS = ans % 998244353;
cout << ANS << "\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 5484kb
input:
3 5 5 2 7 6 7
output:
6
result:
ok 1 number(s): "6"
Test #2:
score: 0
Accepted
time: 2ms
memory: 5492kb
input:
4 2 3 1 6 5 6 4 8
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: 0
Accepted
time: 58ms
memory: 8052kb
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: 5480kb
input:
2 1 1 1000000000000 1000000000000
output:
878392858
result:
wrong answer 1st numbers differ - expected: '276262510', found: '878392858'