QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#440566#8527. Power DivisionsTranscend Lights (Qiwen Xu, Nuo Chen, Fanyou He)#WA 1749ms65400kbC++201.7kb2024-06-13 20:44:312024-06-13 20:45:01

Judging History

This is the latest submission verdict.

  • [2024-06-13 20:45:01]
  • Judged
  • Verdict: WA
  • Time: 1749ms
  • Memory: 65400kb
  • [2024-06-13 20:44:31]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
const int N=3e5+5,M=1e6+5,L=21,P=1e9+7;
int n,a[N],dp[N],mx[L][N];map<pii,int> mp;
ll P1=1000000000000002493,P2=1000000000000002481,val1[M],val2[M],hsh1[N],hsh2[N];
inline int chkmax(int i,int j){return (a[i]>a[j]||a[i]==a[j]&&i<j)?i:j;}
int query(int l,int r){
    int x=log2(r-l+1);
    return chkmax(mx[x][l],mx[x][r-(1<<x)+1]);
}
void solve(int l,int r){
    if(l>r)return;
    int m=query(l,r);solve(l,m-1);dp[m]=(dp[m]+dp[m-1])%P;
    if(m-l>r-m){
        for(int i=a[m]+1;i<=a[m]+L&&i<M;i++)
            for(int j=m;j<=r;j++){
                pii tmp={(hsh1[j]-val1[i]+P1)%P1,(hsh2[j]-val2[i]+P2)%P2};
                if(mp.find(tmp)==mp.end())continue;
                int k=mp[tmp];if(k<l-1||k>=m)continue;dp[j]=(dp[j]+dp[k])%P;
            }
    }
    else{
        for(int i=a[m]+1;i<=a[m]+L&&i<M;i++)
            for(int j=l-1;j<m;j++){
                pii tmp={(hsh1[j]+val1[i])%P1,(hsh2[j]+val2[i])%P2};
                if(mp.find(tmp)==mp.end())continue;
                int k=mp[tmp];if(k<m||k>r)continue;dp[k]=(dp[k]+dp[j])%P;
            }
    }
    solve(m+1,r);
}
int main(){
    ios::sync_with_stdio(false);cin.tie(0);
    cin>>n;for(int i=1;i<=n;i++)cin>>a[i],mx[0][i]=i;val1[0]=val2[0]=1;
    for(int i=1;i<M;i++)val1[i]=2*val1[i-1]%P1,val2[i]=2*val2[i-1]%P2;
    mp[{0,0}]=0;
    for(int i=1;i<=n;i++){
        hsh1[i]=(hsh1[i-1]+val1[a[i]])%P1;
        hsh2[i]=(hsh2[i-1]+val2[a[i]])%P2;
        mp[{hsh1[i],hsh2[i]}]=i;
    }
    for(int j=1;(1<<j)<=n;j++)
        for(int i=1;i<=n-(1<<j)+1;i++)
            mx[j][i]=chkmax(mx[j-1][i],mx[j-1][i+(1<<j-1)]);
    dp[0]=1;solve(1,n);cout<<dp[n]<<"\n";
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 8ms
memory: 21180kb

input:

5
2 0 0 1 1

output:

6

result:

ok 1 number(s): "6"

Test #2:

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

input:

1
0

output:

1

result:

ok 1 number(s): "1"

Test #3:

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

input:

2
1 1

output:

2

result:

ok 1 number(s): "2"

Test #4:

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

input:

3
2 1 1

output:

3

result:

ok 1 number(s): "3"

Test #5:

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

input:

4
3 2 2 3

output:

4

result:

ok 1 number(s): "4"

Test #6:

score: 0
Accepted
time: 6ms
memory: 21352kb

input:

5
3 4 4 2 4

output:

2

result:

ok 1 number(s): "2"

Test #7:

score: 0
Accepted
time: 0ms
memory: 19348kb

input:

7
3 4 3 5 6 3 4

output:

6

result:

ok 1 number(s): "6"

Test #8:

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

input:

10
8 6 5 6 7 8 6 8 9 9

output:

4

result:

ok 1 number(s): "4"

Test #9:

score: 0
Accepted
time: 0ms
memory: 19856kb

input:

96
5 1 0 2 5 5 2 4 2 4 4 2 3 4 0 2 1 4 3 1 2 0 2 2 3 2 4 5 3 5 2 0 2 2 5 3 0 4 5 3 5 4 4 3 1 2 0 5 4 5 0 2 3 2 4 0 0 4 2 0 2 5 3 3 1 5 5 1 1 1 0 5 0 3 0 2 1 1 0 5 0 3 3 4 4 5 3 0 2 2 0 5 4 5 0 5

output:

11332014

result:

ok 1 number(s): "11332014"

Test #10:

score: 0
Accepted
time: 12ms
memory: 19824kb

input:

480
2 0 4 4 1 0 0 3 1 1 4 2 5 5 4 2 1 2 4 4 1 3 4 3 0 5 2 0 2 5 1 0 5 0 0 5 5 0 2 5 2 2 3 1 4 3 5 4 5 2 4 4 4 4 1 4 0 3 4 3 4 1 0 4 3 4 5 4 3 5 0 2 2 0 1 5 4 4 2 0 3 3 3 4 3 0 5 5 3 1 5 1 0 1 0 4 3 0 5 1 4 1 4 3 0 1 3 5 0 3 3 1 0 4 1 1 2 0 1 2 0 3 5 2 0 5 5 5 5 3 5 1 0 2 5 2 2 0 2 0 2 3 5 1 2 1 5 4 ...

output:

506782981

result:

ok 1 number(s): "506782981"

Test #11:

score: 0
Accepted
time: 4ms
memory: 20696kb

input:

2400
0 2 2 0 5 4 3 2 3 2 5 4 5 4 4 5 2 2 4 2 2 0 1 0 5 0 4 4 0 0 5 0 4 0 1 3 4 5 0 3 1 0 4 0 2 5 0 3 3 3 3 1 0 5 5 3 1 3 5 2 4 0 5 0 4 5 4 2 2 1 5 2 2 4 1 0 5 1 5 0 1 2 0 0 3 5 4 0 0 1 1 1 4 2 0 5 1 3 3 5 0 4 4 1 5 5 3 4 4 4 0 2 4 0 5 1 3 1 5 0 5 5 1 3 0 3 1 2 0 1 1 3 5 2 3 4 0 3 0 5 4 0 4 3 5 0 5 2...

output:

586570528

result:

ok 1 number(s): "586570528"

Test #12:

score: 0
Accepted
time: 45ms
memory: 22824kb

input:

12000
2 2 1 2 0 2 5 3 2 0 1 3 2 5 4 0 0 5 3 2 0 2 3 4 3 2 1 4 3 0 3 5 4 1 0 2 4 1 3 2 3 5 0 3 0 0 4 0 4 5 1 0 4 1 1 1 5 4 3 0 3 5 4 5 2 5 0 1 2 3 5 5 2 5 4 2 0 4 4 3 0 0 2 5 0 3 4 2 5 4 2 1 4 5 1 1 2 3 0 3 3 3 3 4 0 5 3 4 0 3 0 2 0 0 2 0 3 4 2 2 0 1 0 5 3 0 2 0 2 2 1 0 5 3 5 4 5 5 0 4 0 4 1 4 4 3 2 ...

output:

201653965

result:

ok 1 number(s): "201653965"

Test #13:

score: 0
Accepted
time: 257ms
memory: 28980kb

input:

60000
2 5 0 3 2 3 5 3 5 5 4 1 1 5 3 0 1 1 2 5 5 5 0 3 2 0 3 2 3 3 0 0 1 4 3 1 4 2 3 3 0 5 1 0 1 1 5 5 4 0 5 4 1 3 1 3 5 3 2 4 4 4 5 4 3 2 3 2 4 5 2 0 4 5 1 2 0 4 0 5 1 3 4 1 2 4 1 1 3 3 0 1 1 3 0 0 2 3 3 2 1 4 1 2 4 3 3 5 2 5 3 4 3 0 2 1 1 1 5 1 2 4 2 3 1 2 1 0 2 0 1 1 5 5 3 4 2 5 2 4 5 3 0 5 1 4 2 ...

output:

592751350

result:

ok 1 number(s): "592751350"

Test #14:

score: 0
Accepted
time: 1749ms
memory: 65376kb

input:

300000
0 5 1 5 5 4 5 3 0 5 0 5 1 4 1 2 2 2 3 0 1 5 4 0 3 1 4 5 2 1 0 3 2 1 2 5 0 2 4 5 0 1 2 1 1 0 0 5 3 0 0 3 4 5 0 2 1 1 1 2 5 1 4 3 1 0 2 0 0 4 3 3 2 5 3 3 1 5 2 0 2 4 3 1 0 3 4 1 3 3 1 0 0 1 1 1 3 1 2 3 5 3 3 2 0 3 0 0 5 5 0 0 0 0 1 4 3 3 4 3 4 5 3 3 5 1 1 4 2 2 1 3 2 1 1 0 0 5 5 0 0 3 2 4 5 5 2...

output:

842503795

result:

ok 1 number(s): "842503795"

Test #15:

score: 0
Accepted
time: 1378ms
memory: 65400kb

input:

300000
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...

output:

432100269

result:

ok 1 number(s): "432100269"

Test #16:

score: -100
Wrong Answer
time: 261ms
memory: 65372kb

input:

300000
1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 10000...

output:

799272944

result:

wrong answer 1st numbers differ - expected: '432100269', found: '799272944'