#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], MX = 0; ll ans = 0; 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())));
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;
update(incr, 1, 1, N, X, DP1[i]);
}
for (int i = N - 1; i >= 0; i--) { int X = getX(A[i]);
DP2[i] = query(decr, 1, 1, N, 1, X - 1); DP2[i].f++; if (DP2[i].s == 0) DP2[i].s = 1;
MX = max(MX, DP1[i].f + DP2[i].f - 1);
update(decr, 1, 1, N, X, DP2[i]);
}
for (int i = 0; i < N; i++) if (DP1[i].f + DP2[i].f - 1 == MX) {
ll prod = (DP1[i].s * DP2[i].s) % MOD;
ans += (prod * powr[N - DP1[i].f - DP2[i].f + 1]) % 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 |
492 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 |
1 ms |
364 KB |
Output is correct |
| 7 |
Incorrect |
3 ms |
492 KB |
Output isn't correct |
| 8 |
Incorrect |
2 ms |
492 KB |
Output isn't correct |
| 9 |
Correct |
2 ms |
492 KB |
Output is correct |
| 10 |
Correct |
3 ms |
640 KB |
Output is correct |
| 11 |
Incorrect |
317 ms |
17388 KB |
Output isn't correct |
| 12 |
Incorrect |
270 ms |
16104 KB |
Output isn't correct |
| 13 |
Incorrect |
244 ms |
12012 KB |
Output isn't correct |
| 14 |
Incorrect |
293 ms |
24424 KB |
Output isn't correct |
| 15 |
Incorrect |
364 ms |
26088 KB |
Output isn't correct |
| 16 |
Incorrect |
416 ms |
27496 KB |
Output isn't correct |
| 17 |
Incorrect |
271 ms |
12028 KB |
Output isn't correct |
| 18 |
Incorrect |
273 ms |
11900 KB |
Output isn't correct |
| 19 |
Incorrect |
289 ms |
11880 KB |
Output isn't correct |
| 20 |
Incorrect |
274 ms |
11752 KB |
Output isn't correct |
