#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[100010]; vector<int> 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] = 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]); }
powr[0] = 1; for (int i = 1; i <= N; i++) powr[i] = (2 * powr[i - 1]) % MOD;
sort(allX.begin(), allX.end()); allX.resize(distance(allX.begin(), unique(allX.begin(), allX.end())));
// cout << MX << endl;
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;
// cout << DP1[i].f << " " << DP2[i].f << endl;
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); // cout << MX << endl;
}
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 << endl;
}
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] = 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] = 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 |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Correct |
1 ms |
376 KB |
Output is correct |
| 5 |
Correct |
1 ms |
384 KB |
Output is correct |
| 6 |
Correct |
1 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 |
Incorrect |
327 ms |
15976 KB |
Output isn't correct |
| 12 |
Incorrect |
266 ms |
15080 KB |
Output isn't correct |
| 13 |
Incorrect |
239 ms |
10988 KB |
Output isn't correct |
| 14 |
Incorrect |
302 ms |
23096 KB |
Output isn't correct |
| 15 |
Incorrect |
383 ms |
24552 KB |
Output isn't correct |
| 16 |
Incorrect |
417 ms |
25596 KB |
Output isn't correct |
| 17 |
Incorrect |
270 ms |
10536 KB |
Output isn't correct |
| 18 |
Incorrect |
275 ms |
10600 KB |
Output isn't correct |
| 19 |
Incorrect |
275 ms |
10600 KB |
Output isn't correct |
| 20 |
Incorrect |
274 ms |
10472 KB |
Output isn't correct |
