QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#742782 | #8177. Sum is Integer | ucup-team3215# | WA | 134ms | 5196kb | C++23 | 2.0kb | 2024-11-13 17:18:32 | 2024-11-13 17:18:33 |
Judging History
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'