QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#325516#8177. Sum is IntegerBUET_POTATOES#WA 234ms22352kbC++202.2kb2024-02-11 15:55:142024-02-11 15:55:16

Judging History

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

  • [2024-02-11 15:55:16]
  • 评测
  • 测评结果:WA
  • 用时:234ms
  • 内存:22352kb
  • [2024-02-11 15:55:14]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
using LL = __int128;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<typename T>
using OST = tree<T,null_type,less<T>,
rb_tree_tag, tree_order_statistics_node_update>;
//find_by_order(k):iterator to kth smallest(0 ind)
//order_of_key(x) :  no of items  < x

const LL M1 = 1e9+7;
const LL M2 = 998244353;
const LL M3 = 1e9+9;

typedef pair<LL, LL> PLL;
LL power(LL a, LL b, LL m) {
  a = (a%m+m)%m; LL ans = 1;
  while (b) {
    if (b & 1) ans = (ans*a)%m;
    a = (a*a)%m; b >>= 1;
  }
  return ans;
}
LL egcd(LL a, LL b, LL &x, LL &y) {
  LL xx = y = 0; LL yy = x = 1;
  while (b) {
    LL q = a/b; LL t = b; b = a%b; a = t;
    t = xx; xx = x-q*xx; x = t;
    t = yy; yy = y-q*yy; y = t;
  }
  return a;
}
LL inverse(LL a, LL m) {
  LL x, y; LL g = egcd(a, m, x, y);
  if (g > 1) return -1; return (x%m+m)%m;
}
PLL CRT(LL m1, LL r1, LL m2, LL r2) {
  LL s, t; LL g = egcd(m1, m2, s, t);
  if (r1%g != r2%g) return PLL(0, -1);
  LL ss = ((s*r2)%m2)*m1, tt = ((t*r1)%m1)*m2;
  LL M = m1*m2, ans = ((ss+tt)%M+M)%M;
  return PLL(ans/g, M/g);
}
PLL CRT(const vector<LL> &m, const vector<LL> &r){
  PLL ans = PLL(r[0], m[0]);
  for (int i = 1; i < m.size(); i++) {
    ans = CRT(ans.second, ans.first, m[i], r[i]);
    if (ans.second == -1) break;
  } return ans;
}


int main(){
    ios::sync_with_stdio(false); cin.tie(0);

    int n;
    cin>>n;

    OST<pair<LL, int>> ost;
    ost.insert({LL(0), -1});

    long long ans = 0;
    LL sum = 0;

    for(int i = 0; i<n; i++){
        long long p, q;
        cin>>p>>q;
        p %= q;

        long long h1 = p * inverse(q, M1) % M1;
        long long h2 = p * inverse(q, M2) % M2;
        long long h3 = p * inverse(q, M3) % M3;

        auto [h, M] = CRT({M1, M2, M3}, {h1, h2, h3});
        sum = (sum + h) % M;

        ans += ost.order_of_key({sum, n+1}) - ost.order_of_key({sum-n, -2}) ; // all (x,i) such that h-n <= x <= h

        ost.insert({sum, i});
    }

    cout<<ans<<endl;

    return 0;
}
/*
4
1 6
1 3
1 2
1 2


5
1 1
2 2
3 3
4 4
5 5


2
1 99999
99999 100000
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

4
1 6
1 3
1 2
1 2

output:

2

result:

ok "2"

Test #2:

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

input:

5
1 1
2 2
3 3
4 4
5 5

output:

15

result:

ok "15"

Test #3:

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

input:

2
1 99999
99999 100000

output:

0

result:

ok "0"

Test #4:

score: -100
Wrong Answer
time: 234ms
memory: 22352kb

input:

200000
82781 82781
86223 86223
16528 16528
84056 84056
94249 94249
54553 54553
25943 25943
10415 10415
52417 52417
46641 46641
70298 70298
84228 84228
55441 55441
49326 49326
11753 11753
89499 89499
58220 58220
71482 71482
32373 32373
7251 7251
78573 78573
74268 74268
46682 46682
20314 20314
85519 8...

output:

19799405515

result:

wrong answer 1st words differ - expected: '10603308211', found: '19799405515'