#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, ll> pii;
#define pb push_back
#define f first
#define s second
int N, A[200010]; ll powr[200010]; vector<ll> allX;
pii incr[800010]; pii decr[800010]; pii DP1[200010], DP2[200010];
const ll MOD = 1000000007LL;
int getX(int X) { return lower_bound(allX.begin(), allX.end(), X) - allX.begin() + 1; }
pii comb(pii A, pii B) { if (A.f != B.f) return max(A, B); return pii {A.f, (A.s + B.s) % MOD}; }
void update(pii tree[], int x, int l, int r, int pos, pii val) { int mid = (l + r) / 2;
if (r < pos || l > pos) return ; if (l == r) { tree[x] = comb(tree[x], val); return ; }
update(tree, 2 * x, l, mid, pos, val); update(tree, 2 * x + 1, mid + 1, r, pos, val);
tree[x] = comb(tree[2 * x], tree[2 * x + 1]);
}
pii query(pii tree[], int x, int l, int r, int tl, int tr) { int mid = (l + r) / 2;
if (r < tl || l > tr) return pii {0, 0}; if (tl <= l && r <= tr) return tree[x];
return comb(query(tree, 2 * x, l, mid, tl, tr), query(tree, 2 * x + 1, mid + 1, r, tl, tr));
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> N; for (int i = 0; i < N; i++) { cin >> A[i]; allX.pb(A[i]); }
sort(allX.begin(), allX.end()); allX.resize(distance(allX.begin(), unique(allX.begin(), allX.end())));
powr[0] = 1; for (int i = 1; i <= N; i++) powr[i] = (2 * powr[i - 1]) % MOD;
int MX = 0; for (int i = N - 1; i >= 0; i--) { int X = getX(A[i]);
DP1[i] = query(incr, 1, 1, N, X + 1, N); DP1[i].f++; if (DP1[i].s == 0) DP1[i].s = 1;
DP2[i] = query(decr, 1, 1, N, 1, X - 1); DP2[i].f++; if (DP2[i].s == 0) DP2[i].s = 1;
update(incr, 1, 1, N, X, DP1[i]); update(decr, 1, 1, N, X, DP2[i]);
MX = max(MX, DP1[i].f + DP2[i].f - 1);
}
ll ans = 0; for (int i = 0; i < N; i++) if (DP1[i].f + DP2[i].f - 1 == MX) { ans += DP1[i].s * DP2[i].s; ans %= MOD; }
ans *= powr[N - MX]; ans %= MOD; cout << MX << " " << ans << "\n";
}
Compilation message
zoltan.cpp: In function 'void update(pii*, int, int, int, int, pii)':
zoltan.cpp:24:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
24 | if (r < pos || l > pos) return ; if (l == r) { tree[x] = comb(tree[x], val); return ; }
| ^~
zoltan.cpp:24:38: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
24 | if (r < pos || l > pos) return ; if (l == r) { tree[x] = comb(tree[x], val); return ; }
| ^~
zoltan.cpp: In function 'pii query(pii*, int, int, int, int, int)':
zoltan.cpp:31:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
31 | if (r < tl || l > tr) return pii {0, 0}; if (tl <= l && r <= tr) return tree[x];
| ^~
zoltan.cpp:31:46: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
31 | if (r < tl || l > tr) return pii {0, 0}; if (tl <= l && r <= tr) return tree[x];
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
364 KB |
Output is correct |
| 4 |
Correct |
1 ms |
364 KB |
Output is correct |
| 5 |
Correct |
1 ms |
364 KB |
Output is correct |
| 6 |
Correct |
0 ms |
364 KB |
Output is correct |
| 7 |
Correct |
2 ms |
492 KB |
Output is correct |
| 8 |
Correct |
2 ms |
492 KB |
Output is correct |
| 9 |
Correct |
2 ms |
492 KB |
Output is correct |
| 10 |
Correct |
2 ms |
492 KB |
Output is correct |
| 11 |
Correct |
330 ms |
25060 KB |
Output is correct |
| 12 |
Correct |
274 ms |
24036 KB |
Output is correct |
| 13 |
Correct |
260 ms |
15336 KB |
Output is correct |
| 14 |
Correct |
384 ms |
24036 KB |
Output is correct |
| 15 |
Correct |
523 ms |
25572 KB |
Output is correct |
| 16 |
Correct |
546 ms |
27168 KB |
Output is correct |
| 17 |
Correct |
420 ms |
24548 KB |
Output is correct |
| 18 |
Correct |
417 ms |
24548 KB |
Output is correct |
| 19 |
Correct |
435 ms |
24548 KB |
Output is correct |
| 20 |
Correct |
417 ms |
24420 KB |
Output is correct |
