QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#313473 | #8180. Bridge Elimination | ucup-team266# | WA | 2ms | 9756kb | C++20 | 2.2kb | 2024-01-24 19:42:48 | 2024-01-24 19:42:49 |
Judging History
answer
/*
Things to notice:
1. do not calculate useless values
2. do not use similar names
Things to check:
1. submit the correct file
2. time (it is log^2 or log)
3. memory
4. prove your naive thoughts
5. long long
6. corner case like n=0,1,inf or n=m
7. check if there is a mistake in the ds or other tools you use
8. fileio in some oi-contest
9. module on time
10. the number of a same divisor in a math problem
11. multi-information and queries for dp and ds problems
*/
#include<bits/stdc++.h>
using namespace std;
#define i128 __int128
#define int long long
#define fi first
#define se second
#define pii pair<long long,long long>
#define mp make_pair
#define pb push_back
i128 mod1=(i128)(1e18);
int mul(int x,int y)
{
i128 tmp=(i128)(x)*(i128)(y);
tmp%=mod1;
return (int)(tmp);
}
int fpow(int x,int b)
{
if(x==0) return 0;
if(b==0) return 1;
int res=1;
while(b>0)
{
if(b&1) res=mul(res,x);
x=mul(x,x);
b>>=1;
}
return res;
}
int N,p[200005],q[200005],s1[200005],buc[200005];
int t[200005];
int lowbit(int x)
{
return x&(-x);
}
void update(int x,int d)
{
x++;
for(int i=x;i<=200001;i+=lowbit(i)) t[i]+=d;
}
int query(int x)
{
x++;
int res=0;
for(int i=x;i>=1;i-=lowbit(i)) res+=t[i];
return res;
}
int getid(int x)
{
return lower_bound(buc,buc+1+N,x)-buc;
}
void solve()
{
cin>>N;
for(int i=1;i<=N;i++)
{
cin>>p[i]>>q[i];
int val=mul(p[i],fpow(q[i],mod1-2));
s1[i]=s1[i-1]+val,s1[i]%=mod1,buc[i]=s1[i];
}
// for(int i=1;i<=N;i++) cout<<s1[i]<<" ";
// cout<<"\n";
sort(buc,buc+1+N);
int ans=0;
for(int i=1;i<=N;i++)
{
update(getid(s1[i-1]),1);
int L=s1[i]-i;
if(L>=0)
{
int ll=lower_bound(buc,buc+1+N,L)-buc;
int rr=upper_bound(buc,buc+1+N,s1[i])-buc-1;
if(ll<=rr) ans+=query(rr)-query(ll-1);
}
else
{
int ll=upper_bound(buc,buc+1+N,s1[i])-buc-1;
if(ll>=0) ans+=query(ll);
L+=mod1;
ll=lower_bound(buc,buc+1+N,L)-buc;
ans+=query(200000)-query(ll-1);
}
}
cout<<ans<<"\n";
}
signed main()
{
mod1+=3;
// for(int i=2;i<=1e9+5;i++) assert(mod1%i);
// cerr<<"...\n";
ios::sync_with_stdio(0);
cin.tie(0);
int _=1;
// cin>>_;
while(_--) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 2ms
memory: 9756kb
input:
3 8 5 9
output:
3
result:
wrong answer 1st words differ - expected: '1102', found: '3'