QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#473868#8527. Power Divisionsw4p3rWA 6ms7648kbC++201.1kb2024-07-12 14:41:302024-07-12 14:41:30

Judging History

This is the latest submission verdict.

  • [2024-07-12 14:41:30]
  • Judged
  • Verdict: WA
  • Time: 6ms
  • Memory: 7648kb
  • [2024-07-12 14:41:30]
  • Submitted

answer

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

#define N 300010
const int mod = int (1e9 + 7);
int n;
int a[N], dp[N];
const int M = int(1e6 + 21);

map<int, vector<int>>ma;
vector<pair<int, int>>All, Last, Now;
vector<int>id[M], g[N];
void calc()
{
    sort(Last.begin(), Last.end());
    for (auto [l, r] : Last)
    {
        for (int L : ma[l - 1])
        {
            Now.push_back({L, r});
            All.push_back({L, r});
        }
        ma[r].push_back(l);
    }
    ma.clear();
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++)cin >> a[i];
    for (int i = 1; i <= n; i ++)id[a[i]].push_back(i);
    for (int w = 1; w < M; w ++)
    {
        for (int x : id[w - 1])Last.push_back({x, x}), All.push_back({x, x});
        calc();
        Last = Now; Now.clear();
    }
    for (auto [l, r] : All)g[r].push_back(l - 1);
    dp[0] = 1;

    for (int i = 1; i <= n; i ++)
    {
        for (int j : g[i])dp[i] = (dp[i] + dp[j]) % mod;
    }
    
    cout << dp[n] << '\n';
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 7648kb

input:

5
2 0 0 1 1

output:

6

result:

ok 1 number(s): "6"

Test #2:

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

input:

1
0

output:

1

result:

ok 1 number(s): "1"

Test #3:

score: 0
Accepted
time: 3ms
memory: 5656kb

input:

2
1 1

output:

2

result:

ok 1 number(s): "2"

Test #4:

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

input:

3
2 1 1

output:

3

result:

ok 1 number(s): "3"

Test #5:

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

input:

4
3 2 2 3

output:

4

result:

ok 1 number(s): "4"

Test #6:

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

input:

5
3 4 4 2 4

output:

2

result:

ok 1 number(s): "2"

Test #7:

score: -100
Wrong Answer
time: 3ms
memory: 5660kb

input:

7
3 4 3 5 6 3 4

output:

1

result:

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