QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#97701#6327. Count Arithmetic Progressionyzc2005WA 99ms8060kbC++142.9kb2023-04-17 22:55:512023-04-17 22:55:55

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-17 22:55:55]
  • 评测
  • 测评结果:WA
  • 用时:99ms
  • 内存:8060kb
  • [2023-04-17 22:55:51]
  • 提交

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 = __int128_t;
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'005;
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;
        if (n == 30) {
            pl = pr = 0;
            rep(i, 1, (int) HL.size() - 1) if (eval(HL[i], l) > eval(HL[i], pl)) pl = i;
            rep(i, 1, (int) HR.size() - 1) if (eval(HR[i], l) > eval(HR[i], pl)) pr = i;
        } else {
            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;
        i128 len = r - l + 1;
        if (vr < 0) down(len, vl / (-diff));
        ans += vl * len + diff * len * (len - 1) / 2;
    }

    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: 5424kb

input:

3
5 5 2
7 6 7

output:

6

result:

ok 1 number(s): "6"

Test #2:

score: 0
Accepted
time: 0ms
memory: 5484kb

input:

4
2 3 1 6
5 6 4 8

output:

0

result:

ok 1 number(s): "0"

Test #3:

score: 0
Accepted
time: 99ms
memory: 8060kb

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: 0
Accepted
time: 3ms
memory: 5496kb

input:

2
1 1
1000000000000 1000000000000

output:

276262510

result:

ok 1 number(s): "276262510"

Test #5:

score: -100
Wrong Answer
time: 1ms
memory: 5484kb

input:

30
1 16647369013 21727798644 51881899844 89018646211 12783831286 65979941759 118839346175 160033057809 126387525649 99120328270 84965287126 196816164175 147276392001 80657019833 203070708878 128172816627 15790836108 155954338058 98235565946 34871844017 57611089069 112660722775 126953918553 639504624...

output:

140596666

result:

wrong answer 1st numbers differ - expected: '604954208', found: '140596666'