#include <bits/stdc++.h>
using namespace std;
int MOD = 1000000007;
class SegTree
{
private:
vector<int> st, count;
int N;
int l(int x) { return (x << 1); }
int r(int x) { return (x << 1) + 1; }
void update(int L, int R, int a, int val, int c, int x)
{
if (L > a || R < a)
return;
if (L == a && R == a)
{
if (val > st[x])
{
st[x] = val;
count[x] = 0;
}
if (val == st[x])
{
count[x] += c;
count[x] = count[x] % MOD;
}
}
else
{
int m = (L + R) / 2;
update(L, m, a, val, c, l(x));
update(m + 1, R, a, val, c, r(x));
st[x] = max(st[l(x)], st[r(x)]);
count[x] = ((st[l(x)] == st[x]) ? count[l(x)] : 0) + ((st[r(x)] == st[x]) ? count[r(x)] : 0);
count[x] = count[x] % MOD;
}
}
pair<int, int> RSQ(int L, int R, int a, int b, int x)
{
if (L > b || R < a)
return {0, 0};
if (L >= a && R <= b)
return {st[x], count[x]};
int m = (L + R) / 2;
pair<int, int> temp1 = RSQ(L, m, a, b, l(x)), temp2 = RSQ(m + 1, R, a, b, r(x));
if (temp1.first < temp2.first)
swap(temp1, temp2);
if (temp1.first == temp2.first)
temp1.second += temp2.second;
temp1.second = temp1.second % MOD;
return temp1;
}
public:
SegTree(int x)
{
N = pow(2, ceil(log2(x)));
st.assign(2 * N, 0);
count.assign(2 * N, 0);
}
void update(int x, int val, int c) { update(0, N - 1, x, val, c, 1); }
pair<int, int> RSQ(int a, int b) { return RSQ(0, N - 1, a, b, 1); }
};
int main()
{
int N;
cin >> N;
vector<int> Tab(N), vals(N);
for (int i = 0; i < N; i++)
{
cin >> Tab[i];
vals[i] = Tab[i];
}
sort(vals.begin(), vals.end());
map<int, int> M;
int buff = 1;
for (int i = 0; i < N; i++)
{
M[vals[i]] = buff++;
}
for (int i = 0; i < N; i++)
Tab[i] = M[Tab[i]];
M.clear();
vals.clear();
vector<pair<long long, long long>> ansleft(N), ansright(N);
SegTree STL(N + 1), STR(N + 1);
long long best = 0;
for (int i = N - 1; i >= 0; i--)
{
ansleft[i] = STL.RSQ(0, Tab[i] - 1);
ansright[i] = STR.RSQ(Tab[i] + 1, N);
ansleft[i].first++, ansright[i].first++;
if (ansleft[i].first == 1)
ansleft[i].second++;
if (ansright[i].first == 1)
ansright[i].second++;
ansleft[i].second = ansleft[i].second % MOD;
ansright[i].second = ansright[i].second % MOD;
STL.update(Tab[i], ansleft[i].first, ansleft[i].second);
STR.update(Tab[i], ansright[i].first, ansright[i].second);
best = max(best, ansright[i].first + ansleft[i].first);
}
long long tot = 0;
for (int i = 0; i < N; i++)
{
if (ansright[i].first + ansleft[i].first == best)
tot = (tot + (ansright[i].second * ansleft[i].second)) % MOD;
}
for (int i = 0; i < N - best + 1; i++)
{
tot = (tot * 2) % MOD;
}
cout << best - 1 << ' ' << tot;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
600 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
1 ms |
348 KB |
Output is correct |
| 8 |
Correct |
2 ms |
348 KB |
Output is correct |
| 9 |
Correct |
1 ms |
348 KB |
Output is correct |
| 10 |
Correct |
1 ms |
348 KB |
Output is correct |
| 11 |
Correct |
197 ms |
15188 KB |
Output is correct |
| 12 |
Correct |
166 ms |
14072 KB |
Output is correct |
| 13 |
Correct |
185 ms |
10400 KB |
Output is correct |
| 14 |
Correct |
206 ms |
13908 KB |
Output is correct |
| 15 |
Correct |
267 ms |
16212 KB |
Output is correct |
| 16 |
Correct |
314 ms |
17236 KB |
Output is correct |
| 17 |
Correct |
249 ms |
17876 KB |
Output is correct |
| 18 |
Correct |
225 ms |
18000 KB |
Output is correct |
| 19 |
Correct |
234 ms |
18000 KB |
Output is correct |
| 20 |
Correct |
240 ms |
17876 KB |
Output is correct |
