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
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
AC × 3
AC × 6
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