#include <bits/stdc++.h>
using namespace std;
int MOD = 1000000007;
class SegTree
{
private:
vector<long long> st, count;
long long N;
long long l(long long x) { return (x << 1); }
long long r(long long x) { return (x << 1) + 1; }
void update(long long L, long long R, long long a, long long val, long long c, long long 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;
}
else
{
long long 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<long long, long long> RSQ(long long L, long long R, long long a, long long b, long long x)
{
if (L > b || R < a)
return {0, 0};
if (L >= a && R <= b)
return {st[x], count[x]};
long long m = (L + R) / 2;
pair<long long, long long> 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(long long x)
{
N = pow(2, ceil(log2(x)));
st.assign(2 * N, 0);
count.assign(2 * N, 0);
}
void update(long long x, long long val, long long c) { update(0, N - 1, x, val, c, 1); }
pair<long long, long long> RSQ(long long a, long long b) { return RSQ(0, N - 1, a, b, 1); }
};
int main()
{
long long N;
cin >> N;
vector<long long> Tab(N), vals(N);
for (long long i = 0; i < N; i++)
{
cin >> Tab[i];
vals[i] = Tab[i];
}
sort(vals.begin(), vals.end());
map<long long, long long> M;
long long buff = 1;
for (long long i = 0; i < N; i++)
{
M[vals[i]] = buff++;
}
for (long long i = 0; i < N; i++)
Tab[i] = M[Tab[i]];
vector<pair<long long, long long>> ansleft(N), ansright(N);
SegTree STL(N + 1), STR(N + 1);
long long best = 0;
for (long long 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 (long long i = 0; i < N; i++)
{
if (ansright[i].first + ansleft[i].first == best)
tot = (tot + (ansright[i].second * ansleft[i].second)) % MOD;
}
for (long long 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 |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
2 ms |
612 KB |
Output is correct |
| 8 |
Correct |
2 ms |
600 KB |
Output is correct |
| 9 |
Correct |
2 ms |
604 KB |
Output is correct |
| 10 |
Correct |
1 ms |
604 KB |
Output is correct |
| 11 |
Runtime error |
235 ms |
35144 KB |
Memory limit exceeded |
| 12 |
Runtime error |
191 ms |
32848 KB |
Memory limit exceeded |
| 13 |
Correct |
203 ms |
23636 KB |
Output is correct |
| 14 |
Runtime error |
235 ms |
33108 KB |
Memory limit exceeded |
| 15 |
Runtime error |
319 ms |
37200 KB |
Memory limit exceeded |
| 16 |
Runtime error |
372 ms |
40524 KB |
Memory limit exceeded |
| 17 |
Runtime error |
268 ms |
37968 KB |
Memory limit exceeded |
| 18 |
Runtime error |
306 ms |
37844 KB |
Memory limit exceeded |
| 19 |
Runtime error |
264 ms |
37968 KB |
Memory limit exceeded |
| 20 |
Runtime error |
267 ms |
37788 KB |
Memory limit exceeded |
