QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#742782#8177. Sum is Integerucup-team3215#WA 134ms5196kbC++232.0kb2024-11-13 17:18:322024-11-13 17:18:33

Judging History

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

  • [2024-11-13 17:18:33]
  • 评测
  • 测评结果:WA
  • 用时:134ms
  • 内存:5196kb
  • [2024-11-13 17:18:32]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

using u64 = uint64_t;
using u128 = __uint128_t;
using u256 = array<u128, 2>;

constexpr u128 mod = (u128)907763202420097943ull << 64 | 12508198021901489645ull, bnd = 3e10;
constexpr int N = 1e5 + 1;

u256 eprod(u128 a, u128 b) {
  u128 x = (u64)(a >> 0) * (u128)(u64)(b >> 0);
  u128 z = (u64)(a >> 64) * (u128)(u64)(b >> 64);
  u128 y = (u64)(a >> 64) * (u128)(u64)(b >> 0) +
           (u64)(a >> 0) * (u128)(u64)(b >> 64);
  u128 ylo = (u64)y;
  u128 yhi = y >> 64;
  u128 lo = x + (ylo << 64);
  u128 hi = yhi + (lo < (ylo << 64)) + z;
  return {hi, lo};
}

u256 dif(u256 a, u256 b) {
  a[0] -= b[0] + (a[1] < b[1]);
  a[1] -= b[1];
  return a;
}

u256 half(u256 a) { return {a[0] / 2, a[1] / 2 + (a[0] % 2 << 127)}; }

u128 red(u256 a) {
  u256 t = {mod, 0};
  for (int i = 129; i--; t = half(t)) if (!(a < t)) a = dif(a, t);
  return a[1];
}

auto& add(auto&& a, auto b) { return a -= (a += b) >= mod? mod: 0; }
auto& mul(auto&& a, auto b) { return a = red(eprod(a, b)); }
u128 fpow(u128 a, u128 b) { u128 r = 1; for (; b; b /= 2, mul(a, a)) if (b % 2) mul(r, a); return r; }

u128 inv[N];

int ft[2 * N];

void upd(int i, int x) { for (; i < 2 * N; i |= i + 1) ft[i] += x; }
int que(int i) { int res = 0 ; for (; i; i &= i - 1) res += ft[i - 1]; return res; }

int main() {
  for (u128 i = 1, f = 1; i < N; ++i) inv[i] = f, mul(f, i);
  for (u128 i = N, f = fpow(inv[N - 1], mod - 2); --i; ) mul(inv[i], f), mul(f, i);
  u128 ps = bnd;
  vector<array<u128, 2>> v{{ps, 1}};
  int n; cin >> n;
  for (int i = 0; i < n; ++i) {
    int p, q; cin >> p >> q;
    add(ps, mul(+inv[q], p));
    assert(ps > bnd);
    v.push_back({ps - bnd, 2 * i + 2});
    v.push_back({ps, 2 * i + 3});
  }
  sort(v.begin(), v.end());
  uint64_t ans = 0;
  for (auto& [_, i]: v) {
    if (i % 2) upd(i / 2, 1);
    if (i % 2) ans += que(i / 2);
    else       ans -= que(i / 2);
  }
  cout << ans << '\n';
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 134ms
memory: 5196kb

input:

4
1 6
1 3
1 2
1 2

output:

6

result:

wrong answer 1st words differ - expected: '2', found: '6'