QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#497940#8712. Flooding WallSirPh#12 167ms61756kbC++204.0kb2024-07-29 20:49:272024-07-29 20:49:28

Judging History

This is the latest submission verdict.

  • [2024-07-29 20:49:28]
  • Judged
  • Verdict: 12
  • Time: 167ms
  • Memory: 61756kb
  • [2024-07-29 20:49:27]
  • Submitted

answer

#include<bits/stdc++.h>
// #define int long long
using namespace std;
const int mod=(int)1e9+7;
vector<vector<int>>dpl;
vector<vector<int>>dpr;
int getsuml(int i,int l,int r)
{
    return (dpl[i][r]-dpl[i][l-1]+mod)%mod;
}
int getsumr(int i,int l,int r)
{
    return (dpr[i][r]-dpr[i][l-1]+mod)%mod;
}
signed main()
{
    int n;
    cin>>n;
    vector<int>arr(n+1);
    vector<int>brr(n+1);
    for(int i=1;i<=n;i++)cin>>arr[i];
    for(int i=1;i<=n;i++)cin>>brr[i];
    set<int>st;
    for(auto i:arr)st.insert(i);
    for(auto i:brr)st.insert(i);
    int cnt=1;
    vector<int>hi;
    hi.push_back(0);
    for(auto i:st)
    {
        cnt++;
        hi.push_back(i);
    }
    int a7a=*max_element(arr.begin(),arr.end());
    a7a=max(a7a,*max_element(brr.begin(),brr.end()));
    a7a=lower_bound(hi.begin(),hi.end(),a7a)-hi.begin();
    dpl.resize(n+2);
    dpr.resize(n+2);
    for(int i=0;i<=n+1;i++)
    {
        dpl[i].resize(a7a+1);
        dpr[i].resize(a7a+1);
    }
    long long ans=0;
    for(int i=1;i<=n;i++)
    {
        // ans=ans-(((arr[i]*((1ll<<(n-1))%mod))%mod)+mod)%mod;
        // ans=ans-(((brr[i]*((1ll<<(n-1))%mod))%mod)+mod)%mod;
    }
    // cout<<dpl.size();
    // return 0;
    dpl[0][0]=1;
    for(int i=1;i<=n;i++)arr[i]=lower_bound(hi.begin(),hi.end(),arr[i])-hi.begin(),brr[i]=lower_bound(hi.begin(),hi.end(),brr[i])-hi.begin();
    for(int i=1;i<=n;i++)
    {
        for(int j=arr[i];j>=0;j--)
        {
            dpl[i][arr[i]]+=dpl[i-1][j];
            if(dpl[i][arr[i]]>=mod)
            dpl[i][arr[i]]-=mod;
        }
        for(int j=arr[i]+1;j<=a7a;j++)
        {
            dpl[i][j]+=dpl[i-1][j];
            if(dpl[i][j]>=mod)
            dpl[i][j]-=mod;
        }
        for(int j=brr[i];j>=0;j--)
        {
            dpl[i][brr[i]]+=dpl[i-1][j];
            if(dpl[i][brr[i]]>=mod)
            dpl[i][brr[i]]-=mod;
        }
        for(int j=brr[i]+1;j<=a7a;j++)
        {
            dpl[i][j]+=dpl[i-1][j];
            if(dpl[i][j]>=mod)
            dpl[i][j]-=mod;
        }
    }
    dpr[n+1][0]=1;
    for(int i=n;i>=1;i--)
    {
        for(int j=arr[i];j>=0;j--)
        {
            dpr[i][arr[i]]+=dpr[i+1][j];
            if(dpr[i][arr[i]]>=mod)
            dpr[i][arr[i]]-=mod;
        }
        for(int j=arr[i]+1;j<=a7a;j++)
        {
            dpr[i][j]+=dpr[i+1][j];
            if(dpr[i][j]>=mod)
            dpr[i][j]-=mod;
        }
        for(int j=brr[i];j>=0;j--)
        {
            dpr[i][brr[i]]+=dpr[i+1][j];
            if(dpr[i][brr[i]]>=mod)
            dpr[i][brr[i]]-=mod;
        }
        for(int j=brr[i]+1;j<=a7a;j++)
        {
            dpr[i][j]+=dpr[i+1][j];
            if(dpr[i][j]>=mod)
            dpr[i][j]-=mod;
        }
    }
    // cout<<ans<<endl;
    for(int i=0;i<=n+1;i++)
        for(int j=1;j<=a7a;j++){
            dpl[i][j]+=dpl[i][j-1];
            if(dpl[i][j]>=mod)
            dpl[i][j]-=mod;
            dpr[i][j]+=dpr[i][j-1];
            if(dpr[i][j]>=mod)
            dpr[i][j]-=mod;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=min(arr[i],brr[i]);j<=a7a;j++)
        {
            if(j>=arr[i]){
            long long x=getsuml(i-1,j,j);
            x*=getsumr(i+1,j,a7a);
            x%=mod;
            ans+=((hi[j]-hi[arr[i]])*x);
            if(ans>=mod)ans-=mod;
            x=getsumr(i+1,j,j);
            x*=getsuml(i-1,j+1,a7a);
            x%=mod;
            ans+=((hi[j]-hi[arr[i]])*x);
            if(ans>=mod)ans-=mod;
            }
            if(j>=brr[i])
            {
                long x=getsuml(i-1,j,j);
                x*=getsumr(i+1,j,a7a);
                x%=mod;
                ans+=((hi[j]-hi[brr[i]])*x);
                if(ans>=mod)ans-=mod;
                x=getsumr(i+1,j,j);
                x*=getsuml(i-1,j+1,a7a);
                x%=mod;
                ans+=((hi[j]-hi[brr[i]])*x);
                if(ans>=mod)ans-=mod;
            }
        }
    }       
    cout<<ans<<endl;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 8
Accepted
time: 0ms
memory: 3732kb

input:

4
1 1 1 1
2 2 2 2

output:

6

result:

ok single line: '6'

Test #2:

score: 8
Accepted
time: 0ms
memory: 3576kb

input:

10
1 2 3 4 5 6 7 8 9 10
10 9 8 7 6 5 4 3 2 1

output:

21116

result:

ok single line: '21116'

Test #3:

score: 8
Accepted
time: 0ms
memory: 3568kb

input:

1
1
2

output:

0

result:

ok single line: '0'

Test #4:

score: 8
Accepted
time: 0ms
memory: 3748kb

input:

2
1 1
2 2

output:

0

result:

ok single line: '0'

Test #5:

score: 8
Accepted
time: 0ms
memory: 3596kb

input:

3
1 1 1
2 2 2

output:

1

result:

ok single line: '1'

Test #6:

score: 8
Accepted
time: 0ms
memory: 3808kb

input:

3
1 1 1
3 2 3

output:

3

result:

ok single line: '3'

Test #7:

score: 8
Accepted
time: 0ms
memory: 3588kb

input:

3
2 1 1
3 2 3

output:

4

result:

ok single line: '4'

Test #8:

score: 8
Accepted
time: 0ms
memory: 3736kb

input:

3
1 1 2
3 2 3

output:

4

result:

ok single line: '4'

Test #9:

score: 8
Accepted
time: 0ms
memory: 3596kb

input:

4
1 1 2 2
2 2 1 1

output:

6

result:

ok single line: '6'

Test #10:

score: 8
Accepted
time: 0ms
memory: 3764kb

input:

3
1 4 4
3 1 1

output:

2

result:

ok single line: '2'

Test #11:

score: 0
Wrong Answer
time: 0ms
memory: 3608kb

input:

20
801072306 297281669 94099424 745640358 822582129 579751930 776707816 425952653 529794053 256263083 615445445 401366545 990263003 967996508 788867983 916880116 837997768 346996508 623409388 122077161
141734988 448434751 822901346 825591177 388082644 468025968 260356829 1164654 537396602 730502935 ...

output:

4668867873670259

result:

wrong answer 1st lines differ - expected: '840988190', found: '4668867873670259'

Subtask #2:

score: 0
Wrong Answer

Test #23:

score: 0
Wrong Answer
time: 1ms
memory: 3744kb

input:

100
948 425 211 688 416 81 356 602 712 954 117 522 797 75 281 491 662 669 78 156 939 526 929 937 916 619 166 777 48 898 449 278 298 714 668 755 679 38 389 602 195 135 672 833 655 541 473 27 596 274 351 353 598 993 837 246 950 99 179 751 481 843 550 195 964 279 806 82 330 599 124 756 649 838 513 625 ...

output:

1086453172044641

result:

wrong answer 1st lines differ - expected: '164439470', found: '1086453172044641'

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Skipped

Dependency #1:

0%

Subtask #5:

score: 12
Accepted

Test #57:

score: 12
Accepted
time: 158ms
memory: 61536kb

input:

500000
1 1 1 1 2 2 2 1 1 1 1 1 2 2 1 1 2 2 2 2 1 2 1 1 2 1 1 1 1 2 1 2 2 1 1 2 2 2 1 1 2 2 2 2 1 2 2 2 2 1 2 2 2 1 2 2 2 1 2 2 2 2 2 2 2 2 1 1 2 1 2 1 2 2 1 2 2 2 2 2 2 2 1 1 1 2 2 2 1 1 2 1 2 2 1 2 2 1 2 2 2 1 2 2 2 2 2 2 2 2 1 1 1 2 1 2 1 1 2 1 2 1 2 2 1 1 2 1 1 1 1 1 2 2 2 2 2 2 1 2 2 1 1 2 1 2 1...

output:

869044223

result:

ok single line: '869044223'

Test #58:

score: 12
Accepted
time: 161ms
memory: 61720kb

input:

499993
1 1 2 1 1 2 1 1 2 1 1 1 2 2 2 2 1 1 1 2 1 1 1 2 2 2 1 1 2 2 1 2 1 2 1 2 1 2 2 2 2 1 1 2 1 2 1 2 2 1 1 2 2 2 2 2 1 1 2 1 1 2 1 1 2 2 2 1 2 2 1 2 1 1 2 1 1 2 1 1 1 1 2 1 1 1 2 2 1 1 2 1 1 1 2 2 2 2 1 1 2 1 2 1 2 2 1 2 1 1 1 1 2 1 1 2 1 2 2 1 2 2 2 2 2 1 2 2 1 1 1 2 1 1 1 1 2 1 1 1 2 1 1 2 1 1 1...

output:

480826834

result:

ok single line: '480826834'

Test #59:

score: 12
Accepted
time: 167ms
memory: 61640kb

input:

500000
2 2 1 1 2 2 2 1 1 2 2 2 2 2 1 1 1 1 1 2 1 2 1 2 1 2 2 1 1 1 2 1 1 1 1 1 1 2 2 2 2 2 2 2 2 1 2 1 2 1 2 1 1 2 1 1 2 2 2 1 2 2 1 2 2 1 2 2 1 1 1 2 1 1 1 2 2 2 1 1 1 1 1 1 1 2 1 1 1 1 1 2 2 1 2 1 2 2 2 1 2 1 1 2 1 2 1 1 2 2 2 1 2 1 2 2 2 2 2 2 1 1 2 2 2 2 1 1 1 1 1 1 2 2 1 1 1 2 1 2 2 2 1 1 1 2 2...

output:

869044223

result:

ok single line: '869044223'

Test #60:

score: 12
Accepted
time: 167ms
memory: 61756kb

input:

499999
2 1 2 2 1 2 1 1 2 1 1 1 2 2 2 1 1 2 2 2 1 1 1 2 2 2 2 2 1 2 2 1 1 2 2 2 2 1 1 2 1 2 2 1 2 2 2 2 2 2 1 2 2 2 2 2 2 1 2 2 2 2 2 1 2 1 2 1 2 1 2 1 1 1 1 1 1 2 1 1 1 1 2 1 2 2 1 1 2 2 1 2 1 1 2 1 2 1 1 2 1 1 1 2 2 1 1 2 2 2 2 2 1 2 1 2 2 1 1 1 2 2 1 1 2 1 1 2 1 1 1 2 1 2 1 1 2 1 2 1 2 1 2 2 2 1 1...

output:

192864306

result:

ok single line: '192864306'

Subtask #6:

score: 0
Skipped

Dependency #1:

0%