QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#108817#6327. Count Arithmetic Progression8BQube#RE 3ms5480kbC++142.7kb2023-05-26 18:12:572023-05-26 18:13:02

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-26 18:13:02]
  • 评测
  • 测评结果:RE
  • 用时:3ms
  • 内存:5480kb
  • [2023-05-26 18:12:57]
  • 提交

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 ...

output:


result: