QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#473868 | #8527. Power Divisions | w4p3r | WA | 6ms | 7648kb | C++20 | 1.1kb | 2024-07-12 14:41:30 | 2024-07-12 14:41:30 |
Judging History
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'