QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#316186#8177. Sum is Integerucup-team191#RE 3ms27320kbC++143.1kb2024-01-27 17:57:532024-01-27 17:57:55

Judging History

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

  • [2024-01-27 17:57:55]
  • 评测
  • 测评结果:RE
  • 用时:3ms
  • 内存:27320kb
  • [2024-01-27 17:57:53]
  • 提交

answer

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
using ull=unsigned long long;
using ll=long long;
using pii=pair<int,int>;
using vi=vector<int>;
using vl=vector<ll>;
#define pb push_back
#define all(a) begin(a),end(a)
#define sz(a) (int)(a).size()

const int N=500010,MOD=1e9+7,M=1<<19;
const char en='\n';
const ll LLINF=1ll<<60;

ull modadd(ull a,ull b,ull mod)
{
	if (a+b>=mod) return a+b-mod;
	return a+b;
}

ull modsub(ull a,ull b,ull mod)
{
	if (a>=b) return a-b;
	return a+mod-b;
}

ull modmul(ull a,ull b,ull M)
{
	ll ret = a * b - M * ull(1.L / M * a * b);
	return ret + M * (ret < 0) - M * (ret >= (ll) M);
}

ull modpow(ull b,ull e,ull mod)
{
	ull ans=1;
	for (;e;b=modmul(b,b,mod),e/=2) if (e&1) ans=modmul(ans,b,mod);
	return ans;
}

ull modinv(ull a,ull mod)
{
	return modpow(a,mod-2,mod);
}

bool isPrime(ull n)
{
	if (n<2 || n%6%4!=1) return (n|1)==3;
	ull A[]={2,325,9375,28178,450775,9780504,1795265022};
	ull s=__builtin_ctzll(n-1),d=n>>s;
	for (ull a: A)
	{
		ull p=modpow(a%n,d,n),i=s;
		while (p!=1 && p!=n-1 && a%n && i--) p=modmul(p,p,n);
		if (p!=n-1 && i!=s) return 0;
	}
	return 1;
}

int n,p[N],q[N];
ull v1[N],v2[N],pr1[N],pr2[N];
vector<pair<pii,int>> qu[N];
vi app[N];
int seg[M*2+10];

void upd(int i,int x)
{
	for (i+=M;i;i/=2) seg[i]+=x;
}

int ge(int l,int r,int lo=0,int hi=M,int i=1)
{
	if (lo>=l && hi<=r) return seg[i];
	if (lo>=r || hi<=l) return 0;
	int mid=(lo+hi)/2;
	return ge(l,r,lo,mid,i*2)+ge(l,r,mid,hi,i*2+1);
}

vector<ull> vals;

int toInd(ull x)
{
	return lower_bound(all(vals),x)-vals.begin();
}

pii toInd(pair<ull,ull> x)
{
	return {toInd(x.x),toInd(x.y)};
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	mt19937_64 rng(3892);
	uniform_int_distribution<ull> dist(1e18,2e18);
	ull p1=dist(rng);
	while (!isPrime(p1)) p1=dist(rng);
	ull p2=dist(rng);
	while (!isPrime(p2)) p2=dist(rng);
	ull maxdif=1e10;
	vals.pb(0);
	vals.pb(p1);
	vals.pb(p2);
	cin>>n;
	for (int i=0;i<n;++i)
	{
		cin>>p[i]>>q[i];
		v1[i]=modmul(p[i],modinv(q[i],p1),p1);
		v2[i]=modmul(p[i],modinv(q[i],p2),p2);
		pr1[i+1]=modadd(pr1[i],v1[i],p1);
		pr2[i+1]=modadd(pr2[i],v2[i],p2);
		vals.pb(pr1[i+1]);
		vals.pb(pr2[i+1]);
		vals.pb(modsub(pr1[i+1],maxdif,p1));
		vals.pb(modsub(pr2[i+1],maxdif,p2));
	}
	sort(all(vals));
	vals.erase(unique(all(vals)),vals.end());
	for (int i=0;i<=n;++i) app[toInd(pr1[i])].pb(toInd(pr2[i]));
	for (int i=1;i<=n;++i)
	{
		vector<pair<ull,ull>> i1,i2;
		ull x=pr1[i];
		if (x>=maxdif)
		{
			i1.pb({x-maxdif,x});
		}
		else
		{
			i1.pb({x+p1-maxdif,p1});
			i1.pb({0,x});
		}
		x=pr2[i];
		if (x>=maxdif)
		{
			i2.pb({x-maxdif,x});
		}
		else
		{
			i2.pb({x+p2-maxdif,p2});
			i2.pb({0,x});
		}
		for (auto x: i1)
		{
			for (auto y: i2) qu[toInd(x.y)].pb({toInd(y),1});
			for (auto y: i2) qu[toInd(x.x)].pb({toInd(y),-1});
		}
	}
	ll an=0;
	for (int i=0;i<=(int)vals.size();++i)
	{
		for (auto x: qu[i]) an+=x.y*ge(x.x.x,x.x.y);
		for (auto x: app[i]) upd(x,1);
	}
	cout<<an<<en;
}

詳細信息

Test #1:

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

input:

4
1 6
1 3
1 2
1 2

output:

2

result:

ok "2"

Test #2:

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

input:

5
1 1
2 2
3 3
4 4
5 5

output:

15

result:

ok "15"

Test #3:

score: 0
Accepted
time: 3ms
memory: 27204kb

input:

2
1 99999
99999 100000

output:

0

result:

ok "0"

Test #4:

score: -100
Runtime Error

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:


result: