QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#103041#6327. Count Arithmetic ProgressionAlpha_Q#WA 71ms8132kbC++173.3kb2023-05-04 05:18:212023-05-04 05:18:23

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-04 05:18:23]
  • 评测
  • 测评结果:WA
  • 用时:71ms
  • 内存:8132kb
  • [2023-05-04 05:18:21]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 300010;
const ll INF = 1e17 + 69;
const int MOD = 998244353;
const ll INV_2 = 1 + MOD >> 1;

int n;
ll l[N], r[N];

inline bool bad (pair <ll, ll> A, pair <ll, ll> B, pair <ll, ll> C) {
  return (__int128) (A.second - C.second) * (B.first - A.first) <= (__int128) (A.second - B.second) * (C.first - A.first);
}

inline ll floor (ll x, ll y) {
  if (x % y == 0) return x / y;
  return x < 0 ? x / y - 1 : x / y;
}

inline ll ceiling (ll x, ll y) {
  if (x % y == 0) return x / y;
  return x > 0 ? x / y + 1 : x / y;
}

inline ll range (ll l, ll r) {
  if (l >= r) return 0;
  ll gap = (r - l) % MOD * INV_2 % MOD, ret = (l + r - 1) % MOD * gap % MOD;
  return ret < 0 ? ret + MOD : ret;
}

int main() {
  cin >> n;
  for (int i = 1; i <= n; ++i) scanf("%lld", l + i);
  for (int i = 1; i <= n; ++i) scanf("%lld", r + i);
  vector <array <ll, 3>> L, R;
  vector <ll> events({-INF, INF});
  {
    vector <pair <ll, ll>> vec;
    for (int i = n; i >= 1; --i) {
      pair <ll, ll> cur(1 - i, l[i]);
      while (vec.size() >= 2 and bad(vec[vec.size() - 2], vec.back(), cur)) vec.pop_back();
      vec.emplace_back(cur); 
    }
    ll last = -INF;
    for (int i = 0; i < vec.size(); ++i) {
      if (i + 1 == vec.size()) {
        L.push_back({INF, vec[i].first, vec[i].second});
        break;
      }
      ll at = ceiling(vec[i].second - vec[i + 1].second, vec[i + 1].first - vec[i].first);
      L.push_back({at, vec[i].first, vec[i].second}), events.emplace_back(at), last = at;
    }
  }
  {
    vector <pair <ll, ll>> vec;
    for (int i = 1; i <= n; ++i) {
      pair <ll, ll> cur(i - 1, -r[i]);
      while (vec.size() >= 2 and bad(vec[vec.size() - 2], vec.back(), cur)) vec.pop_back();
      vec.emplace_back(cur); 
    }
    ll last = -INF;
    for (int i = 0; i < vec.size(); ++i) {
      if (i + 1 == vec.size()) {
        R.push_back({INF, vec[i].first, vec[i].second});
        break;
      }
      ll at = ceiling(vec[i].second - vec[i + 1].second, vec[i + 1].first - vec[i].first);
      R.push_back({at, vec[i].first, vec[i].second}), events.emplace_back(at), last = at;
    }
  }
  sort(events.begin(), events.end());
  events.erase(unique(events.begin(), events.end()), events.end());
  ll ans = 0;
  int L_at = 0, R_at = 0;
  for (int i = 0; i + 1 < events.size(); ++i) {
    ll inc = events[i], exc = events[i + 1];
    if (L[L_at][0] == inc) ++L_at;
    if (R[R_at][0] == inc) ++R_at;
    ll l_a = L[L_at][1], l_b = L[L_at][2];
    ll r_a = -R[R_at][1], r_b = -R[R_at][2];
    if (l_a == r_a) {
      if (l_b > r_b) continue;
      ll gap = (exc - inc) % MOD, cur = (r_b - l_b + 1) % MOD * gap;
      ans += cur, ans %= MOD;
    } else {
      if (l_a < r_a) {
        ll lo = min(exc, max(inc, ceiling(l_b - r_b, r_a - l_a)));
        ll gap = exc - lo, cur = (r_b - l_b + 1) % MOD * gap % MOD + (r_a - l_a) * range(lo, exc) % MOD;
        ans += cur, ans %= MOD;
      } else {
        ll hi = max(inc, min(exc, floor(r_b - l_b, l_a - r_a) + 1));
        ll gap = hi - inc, cur = (r_b - l_b + 1) % MOD * gap % MOD + (r_a - l_a) * range(inc, hi) % MOD;
        ans += cur, ans %= MOD;
      }
    }
  }
  ans += MOD, ans %= MOD;
  cout << ans << '\n';
  return 0;
}


Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 5664kb

input:

3
5 5 2
7 6 7

output:

6

result:

ok 1 number(s): "6"

Test #2:

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

input:

4
2 3 1 6
5 6 4 8

output:

0

result:

ok 1 number(s): "0"

Test #3:

score: 0
Accepted
time: 71ms
memory: 8132kb

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

input:

2
1 1
1000000000000 1000000000000

output:

712821071

result:

wrong answer 1st numbers differ - expected: '276262510', found: '712821071'