Submission #4028468
Source Code Expand
#include<bits/stdc++.h>
using namespace std;
#define p 1000000007ll
#define N 200005
#define ll long long
//ll n,len,l,r,ans,inv[N],mul[N],mulinv[N],Ans[N];
ll n,len,l,r,inv[N],Ans[N],mul[N],mulinv[N],ans;
struct node{
ll l,r,id;
};
node q[N];
bool cmp(node a,node b){return(a.l/len)^(b.l/len)?a.l<b.l:((a.l/len)&1)?a.r<b.r:a.r>b.r;}
ll C(ll n,ll m){return((mul[n]*mulinv[m])%p*mulinv[n-m])%p;}
void change1(){ans=(((2*ans)%p-C(l,r))%p+p)%p;}
void change2(){ans=((inv[2]*((ans+C(l,r))%p))%p+p)%p;}
void change3(){ans=((ans+C(l,r))%p+p)%p;}
void change4(){ans=((ans-C(l,r))%p+p)%p;}
int main()
{
scanf("%lld",&n);
len=sqrt(n);
int i;
inv[1]=1,mul[0]=mulinv[0]=1;
for(i=2;i<=100000;i++)inv[i]=(-(p/i)%p*inv[p%i]%p+p)%p;
for(i=1;i<=100000;i++)
{
mul[i]=(mul[i-1]*i)%p;
mulinv[i]=(mulinv[i-1]*inv[i])%p;
}
for(i=1;i<=n;i++)
{
scanf("%lld%lld",&q[i].l,&q[i].r);
q[i].id = i;
}
sort(q+1,q+n+1,cmp);
l=1;r=0;ans=1;
for(i=1;i<=n;i++)
{
while (l<q[i].l){change1();l++;}
while (l>q[i].l){l--;change2();}
while (r<q[i].r){r++;change3();}
while (r>q[i].r){change4();r--;}
Ans[q[i].id]=ans;
}
for(i=1;i<=n;i++) printf("%lld\n",Ans[i]);
return 0;
}
Submission Info
Submission Time
2019-01-17 09:10:45+0900
Task
D - 高橋君
User
luogu_bot5
Language
C++ (GCC 5.4.1)
Score
0
Code Size
1330 Byte
Status
WA
Exec Time
402 ms
Memory
11392 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:20:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld",&n);
^
./Main.cpp:32:42: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld",&q[i].l,&q[i].r);
^
Judge Result
Set Name
sub
All
Score / Max Score
0 / 50
0 / 150
Status
Set Name
Test Cases
sub
test_02E.txt, test_03E.txt, test_05E.txt
All
sample_01.txt, test_01.txt, test_02E.txt, test_03E.txt, test_04.txt, test_05E.txt
Case Name
Status
Exec Time
Memory
sample_01.txt
AC
8 ms
6400 KB
test_01.txt
WA
402 ms
11392 KB
test_02E.txt
WA
195 ms
11392 KB
test_03E.txt
WA
155 ms
11392 KB
test_04.txt
AC
93 ms
11392 KB
test_05E.txt
WA
104 ms
11392 KB