QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#316186 | #8177. Sum is Integer | ucup-team191# | RE | 3ms | 27320kb | C++14 | 3.1kb | 2024-01-27 17:57:53 | 2024-01-27 17:57:55 |
Judging History
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...