QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#181879 | #6327. Count Arithmetic Progression | ucup-team228 | WA | 42ms | 8160kb | C++20 | 12.9kb | 2023-09-17 02:36:41 | 2023-09-17 02:36:42 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#if __SIZEOF_INT128__ >= 16
typedef __int128 LL;
istream& operator>>(istream& in, __int128& a) { int64_t b; in >> b; a = b; return in; }
ostream& operator<<(ostream& out, const __int128 a) {
unsigned __int128 b = a < 0 ? -a : a; char buf[128]; char* c = end(buf); do { --c; *c = "0123456789"[b % 10]; b /= 10; } while (b);
if (a < 0) { --c; *c = '-'; } int64_t len = end(buf) - c; out.rdbuf()->sputn(c, len); return out;
}
#endif
typedef long long ll;
typedef long double ld;
typedef __int128_t LL;
// Redefine epsilon and infinity as necessary. Be mindful of precision errors.
const ld eps = 1e-9, inf = 1e18;
// Basic point/vector struct.
struct Point {
ld x, y;
explicit Point(ld x = 0, ld y = 0) : x(x), y(y) {}
// Addition, substraction, multiply by constant, dot product, cross product.
friend Point operator + (const Point& p, const Point& q) {
return Point(p.x + q.x, p.y + q.y);
}
friend Point operator - (const Point& p, const Point& q) {
return Point(p.x - q.x, p.y - q.y);
}
friend Point operator * (const Point& p, const ld& k) {
return Point(p.x * k, p.y * k);
}
friend ld dot(const Point& p, const Point& q) {
return p.x * q.x + p.y * q.y;
}
friend ld cross(const Point& p, const Point& q) {
return p.x * q.y - p.y * q.x;
}
bool operator==(const Point& ot) const {
return abs(x - ot.x) <= eps && abs(y - ot.y) <= eps;
}
};
ostream& operator<<(ostream& ostr, const Point& p) {
return ostr << "(" << p.x << ", " << p.y << ")";
}
// Basic half-plane struct.
struct Halfplane {
// 'p' is a passing point of the line and 'pq' is the direction vector of the line.
Point p, pq;
ld angle;
char col;
Halfplane() {}
Halfplane(const Point& a, const Point& b, char _col = 'w') : p(a), pq(b - a), col(_col) {
angle = atan2l(pq.y, pq.x);
}
// Check if point 'r' is outside this half-plane.
// Every half-plane allows the region to the LEFT of its line.
bool out(const Point& r) {
return cross(pq, r - p) < -eps;
}
// Comparator for sorting.
bool operator < (const Halfplane& e) const {
return angle < e.angle;
}
// Intersection point of the lines of two half-planes. It is assumed they're never parallel.
friend Point inter(const Halfplane& s, const Halfplane& t) {
ld alpha = cross((t.p - s.p), t.pq) / cross(s.pq, t.pq);
return s.p + (s.pq * alpha);
}
};
ostream& operator<<(ostream& ostr, const Halfplane& hp) {
return ostr << hp.p << "->" << hp.pq << " : " << hp.col;
}
// Actual algorithm
vector<Point> hp_intersect(vector<Halfplane> H) {
Point box[4] = { // Bounding box in CCW order
Point(inf, inf),
Point(-inf, inf),
Point(-inf, -inf),
Point(inf, -inf)
};
for(int i = 0; i<4; i++) { // Add bounding box half-planes.
Halfplane aux(box[i], box[(i+1) % 4]);
H.push_back(aux);
}
// Sort by angle and start algorithm
sort(H.begin(), H.end());
// for (int i = 0; i < H.size(); i++) {
// cout << i << " : " << H[i] << "\n";
// }
// cout << "\n";
deque<Halfplane> dq;
int len = 0;
for(int i = 0; i < int(H.size()); i++) {
// Remove from the back of the deque while last half-plane is redundant
while (len > 1 && H[i].out(inter(dq[len-1], dq[len-2]))) {
dq.pop_back();
--len;
}
// Remove from the front of the deque while first half-plane is redundant
while (len > 1 && H[i].out(inter(dq[0], dq[1]))) {
dq.pop_front();
--len;
}
// Special case check: Parallel half-planes
if (len > 0 && fabsl(cross(H[i].pq, dq[len-1].pq)) < eps) {
// Opposite parallel half-planes that ended up checked against each other.
if (dot(H[i].pq, dq[len-1].pq) < 0.0)
return vector<Point>();
// Same direction half-plane: keep only the leftmost half-plane.
if (H[i].out(dq[len-1].p)) {
dq.pop_back();
--len;
}
else continue;
}
// Add new half-plane
dq.push_back(H[i]);
++len;
// if (i == 8) {
// cout << len << "\n";
// for (int j = 0; j < len; j++) {
// cout << dq[j] << "\n";
// }
// }
}
// Final cleanup: Check half-planes at the front against the back and vice-versa
while (len > 2 && dq[0].out(inter(dq[len-1], dq[len-2]))) {
dq.pop_back();
--len;
}
while (len > 2 && dq[len-1].out(inter(dq[0], dq[1]))) {
dq.pop_front();
--len;
}
// Report empty intersection if necessary
if (len < 3) return vector<Point>();
// Reconstruct the convex polygon from the remaining half-planes.
vector<Point> ret(len);
for(int i = 0; i+1 < len; i++) {
ret[i] = inter(dq[i], dq[i+1]);
}
ret.back() = inter(dq[len-1], dq[0]);
return ret;
}
const int mod = 998244353;
const int N = 3e5 + 10;
ll l[N], r[N];
LL calc_seg(LL lef, LL rig, LL lef_y, LL rig_y) {
if (lef_y > rig_y) {
swap(lef_y, rig_y);
}
if (lef == rig) {
return rig_y - lef_y + 1;
} else if (lef_y == rig_y) {
return rig - lef + 1;
} else {
LL x = rig - lef;
LL y = rig_y - lef_y;
return __gcd(x, y) + 1;
}
}
LL calc_trap(LL lef, LL rig, LL lef_y, LL rig_y) {
if (lef_y > rig_y) {
swap(lef_y, rig_y);
}
if (lef == rig) {
return rig_y + 1;
} else {
LL s2 = (rig - lef) * (lef_y + rig_y);
LL s = s2 / 2;
LL bnd = calc_seg(lef, rig, lef_y, rig_y) + lef_y + rig_y + rig - lef - 1;
return s + bnd / 2 + 1 + ((s2 & 1) && (bnd & 1));
}
}
ll div_down(ll x, ll y) {
if (x >= 0) {
return x / y;
} else {
x *= -1;
return -((x + y - 1) / y);
}
}
ll div_up(ll x, ll y) {
if (x >= 0) {
return (x + y - 1) / y;
} else {
x *= -1;
return -(x / y);
}
}
int solve(int n) {
vector<int> same;
for (int i = 1; i <= n; i++) {
if (l[i] == r[i]) {
same.push_back(i);
}
}
if (same.size() >= 2) {
int x = same[0];
int y = same[1];
if ((r[y] - r[x]) % (y - x) != 0) {
return 0;
}
ll d = (r[y] - r[x]) / (y - x);
ll a0 = r[x] - d * x;
for (int i = 1; i <= n; i++) {
if (l[i] > a0 + d * i || a0 + d * i > r[i]) {
return 0;
}
}
return 1;
} else if (same.size() == 1) {
int id = same[0];
ll x = r[id];
ll lef = -1e12;
ll rig = 1e12;
for (int i = id + 1; i <= n; i++) {
rig = min(rig, div_down(r[i] - x, i - id));
lef = max(lef, div_up(l[i] - x, i - id));
}
for (int i = id - 1; i >= 1; i--) {
rig = min(rig, div_down(x - l[i], id - i));
lef = max(lef, div_up(x - r[i], id - i));
}
return lef <= rig ? (rig - lef + 1) % mod : 0;
}
vector<Halfplane> a;
for (int i = 1; i <= n; i++) {
Halfplane upb(Point{1, ld(-i + r[i])}, Point{0, ld(r[i])});
Halfplane lowb(Point{0, ld(l[i])}, Point{1, ld(-i + l[i])});
a.push_back(upb);
a.push_back(lowb);
}
vector<Point> b = hp_intersect(a);
if (b.size() <= 100) {
for (auto p : b) {
for (auto hp : a) {
if (hp.out(p)) {
return 0;
}
}
}
}
if (b.empty()) {
return 0;
} else {
ld min_y = 0;
for (auto& p : b) {
min_y = min(min_y, p.y);
}
min_y = floor(min_y);
for (auto& p : b) {
p.y -= min_y;
}
int min_pos = 0;
for (int i = 0; i < b.size(); i++) {
if (b[i].x < b[min_pos].x) {
min_pos = i;
}
}
vector<Point> c;
for (int i = min_pos; i < b.size(); i++) {
c.push_back(b[i]);
}
for (int i = 0; i < min_pos; i++) {
c.push_back(b[i]);
}
int max_pos = 0;
for (int i = 0; i < c.size(); i++) {
if (c[i].x > c[max_pos].x) {
max_pos = i;
}
}
vector<Point> lower, upper;
for (int i = 0; i <= max_pos; i++) {
lower.push_back(c[i]);
}
upper.push_back(c[0]);
for (int i = int(c.size()) - 1; i >= max_pos; i--) {
upper.push_back(c[i]);
}
LL ans = 0;
lower.erase(unique(lower.begin(), lower.end()), lower.end());
upper.erase(unique(upper.begin(), upper.end()), upper.end());
for (int i = 0; i + 1 < upper.size(); i++) {
ld lef_ld = upper[i].x + eps;
ld rig_ld = upper[i + 1].x - eps;
LL lef = ceil(lef_ld);
LL rig = floor(rig_ld);
if (lef > rig) {
continue;
}
ld ang = (upper[i + 1].y - upper[i].y) / (upper[i + 1].x - upper[i].x);
LL lef_y = round(upper[i].y + ang * (lef - upper[i].x));
LL rig_y = round(upper[i].y + ang * (rig - upper[i].x));
ans += calc_trap(lef, rig, lef_y, rig_y);
// cout << lef << " " << rig << " " << lef_y << " " << rig_y << " " << calc_trap(lef, rig, lef_y, rig_y) << "\n";
}
for (int i = 0; i < upper.size(); i++) {
auto p = upper[i];
if (abs(p.x - round(p.x)) < eps) {
ans += LL(floor(p.y)) + 1;
// cout << floor(p.y) + 1 << "\n";
}
}
for (int i = 0; i + 1 < lower.size(); i++) {
ld lef_ld = lower[i].x + eps;
ld rig_ld = lower[i + 1].x - eps;
LL lef = ceil(lef_ld);
LL rig = floor(rig_ld);
if (lef > rig) {
continue;
}
ld ang = (lower[i + 1].y - lower[i].y) / (lower[i + 1].x - lower[i].x);
LL lef_y = round(lower[i].y + ang * (lef - lower[i].x));
LL rig_y = round(lower[i].y + ang * (rig - lower[i].x));
ans -= calc_trap(lef, rig, lef_y, rig_y) - calc_seg(lef, rig, lef_y, rig_y);
// cout << lef << " " << rig << " " << lef_y << " " << rig_y << " " << calc_trap(lef, rig, lef_y, rig_y) - calc_seg(lef, rig, lef_y, rig_y) << "\n";
}
for (int i = 0; i < lower.size(); i++) {
auto p = lower[i];
if (abs(p.x - round(p.x)) < eps) {
ans -= LL(floor(p.y));
// cout << floor(p.y) << "\n";
}
}
return ans % mod;
}
}
int slow(int n) {
int res = 0;
for (ll x = l[1]; x <= r[1]; x++) {
for (ll y = l[2]; y <= r[2]; y++) {
bool ok = true;
ll d = y - x;
for (int i = 3; i <= n; i++) {
ok &= (l[i] <= x + d * (i - 1)) && (x + d * (i - 1) <= r[i]);
}
if (ok) {
res++;
if (res == mod) {
res = 0;
}
}
}
}
return res;
}
void stress() {
mt19937 rnd;
while (true) {
int n = rnd() % 5 + 2;
for (int i = 1; i <= n; i++) {
l[i] = rnd() % 10 + 1;
r[i] = rnd() % 10 + 1;
if (l[i] > r[i]) {
swap(l[i], r[i]);
}
}
int ans = solve(n);
int res = slow(n);
if (ans == res) {
cout << "OK" << endl;
} else {
cout << "WA\n";
cout << n << "\n";
for (int i = 1; i <= n; i++) {
cout << l[i] << " ";
}
cout << "\n";
for (int i = 1; i <= n; i++) {
cout << r[i] << " ";
}
cout << "\n\n";
cout << ans << " " << res << "\n";
break;
}
}
exit(0);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
#ifdef LOCAL
freopen("input.txt", "r", stdin);
#endif
// stress();
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> l[i];
}
for (int i = 1; i <= n; i++) {
cin >> r[i];
}
// n = 3e5;
// for (int i = 1; i <= n; i++) {
// l[i] = 1;
// r[i] = 1'000'000'000'000;
// }
cout << solve(n) << "\n";
#ifdef LOCAL
cout << "\nTime elapsed: " << double(clock()) / CLOCKS_PER_SEC << " s.\n";
#endif
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 5556kb
input:
3 5 5 2 7 6 7
output:
6
result:
ok 1 number(s): "6"
Test #2:
score: 0
Accepted
time: 1ms
memory: 5528kb
input:
4 2 3 1 6 5 6 4 8
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: 0
Accepted
time: 42ms
memory: 8160kb
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: 1ms
memory: 5588kb
input:
2 1 1 1000000000000 1000000000000
output:
276262512
result:
wrong answer 1st numbers differ - expected: '276262510', found: '276262512'