QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#313473#8180. Bridge Eliminationucup-team266#WA 2ms9756kbC++202.2kb2024-01-24 19:42:482024-01-24 19:42:49

Judging History

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

  • [2024-01-24 19:42:49]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:9756kb
  • [2024-01-24 19:42:48]
  • 提交

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'