QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#181879#6327. Count Arithmetic Progressionucup-team228WA 42ms8160kbC++2012.9kb2023-09-17 02:36:412023-09-17 02:36:42

Judging History

你现在查看的是最新测评结果

  • [2023-09-17 02:36:42]
  • 评测
  • 测评结果:WA
  • 用时:42ms
  • 内存:8160kb
  • [2023-09-17 02:36:41]
  • 提交

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'