Submission #4028490
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],Ans[N],mul[N],mulinv[N];
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:20:17+0900
Task
D - 高橋君
User
luogu_bot1
Language
C++ (GCC 5.4.1)
Score
200
Code Size
1278 Byte
Status
AC
Exec Time
404 ms
Memory
11392 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:19:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld",&n);
^
./Main.cpp:31: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
50 / 50
150 / 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
AC
404 ms
11392 KB
test_02E.txt
AC
196 ms
11392 KB
test_03E.txt
AC
155 ms
11392 KB
test_04.txt
AC
95 ms
11392 KB
test_05E.txt
AC
105 ms
11392 KB