| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 996884 |
2024-06-11T11:45:51 Z |
otarius |
Zoltan (COCI16_zoltan) |
C++17 |
|
222 ms |
22204 KB |
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define sc second
#define int long long
#define ll long long
#define pii pair<int, int>
#define pb push_back
const ll mod = 1e9 + 9;
const ll inf = 1e9 + 7;
pii inc[800040], der[800040];
pii getinc(int v, int tl, int tr, int l, int r) {
if (l > r) return {0, 0};
if (tl == l && tr == r)
return inc[v];
int tm = (tl + tr) / 2;
pii x = getinc(2 * v, tl, tm, l, min(r, tm));
pii y = getinc(2 * v + 1, tm + 1, tr, max(l, tm + 1), r);
if (x.ff == y.ff) return {x.ff, (x.sc + y.sc) % inf};
return max(x, y);
}
pii getder(int v, int tl, int tr, int l, int r) {
if (l > r) return {0, 0};
if (tl == l && tr == r)
return der[v];
int tm = (tl + tr) / 2;
pii x = getder(2 * v, tl, tm, l, min(r, tm));
pii y = getder(2 * v + 1, tm + 1, tr, max(l, tm + 1), r);
if (x.ff == y.ff) return {x.ff, (x.sc + y.sc) % inf};
return max(x, y);
}
void updinc(int v, int tl, int tr, int pos, pii val) {
if (tl == tr) {
inc[v] = val;
return;
} int tm = (tl + tr) / 2;
if (pos <= tm) updinc(2 * v, tl, tm, pos, val);
else updinc(2 * v + 1, tm + 1, tr, pos, val);
if (inc[2 * v].ff == inc[2 * v + 1].ff) inc[v] = {inc[2 * v].ff, (inc[2 * v].sc + inc[2 * v + 1].sc) % inf};
else inc[v] = max(inc[2 * v], inc[2 * v + 1]);
}
void updder(int v, int tl, int tr, int pos, pii val) {
if (tl == tr) {
der[v] = val;
return;
} int tm = (tl + tr) / 2;
if (pos <= tm) updder(2 * v, tl, tm, pos, val);
else updder(2 * v + 1, tm + 1, tr, pos, val);
if (der[2 * v].ff == der[2 * v + 1].ff) der[v] = {der[2 * v].ff, (der[2 * v].sc + der[2 * v + 1].sc) % inf};
else der[v] = max(der[2 * v], der[2 * v + 1]);
}
ll binpow(ll a, ll b) {
a %= inf;
if (!b) return 1;
if (b & 1) return a * binpow(a, b - 1) % inf;
return binpow(a * a, b >> 1) % inf;
}
void solve() {
int n;
cin >> n;
vector<int> v;
int arr[n + 1];
for (int i = 1; i <= n; i++) {
cin >> arr[i]; v.pb(arr[i]);
} sort(v.begin(), v.end());
v.resize(unique(v.begin(), v.end()) - v.begin());
for (int i = 1; i <= n; i++)
arr[i] = lower_bound(v.begin(), v.end(), arr[i]) - v.begin() + 1;
pii ans = {0, 0};
for (int i = n; i >= 1; i--) {
pii up = getinc(1, 1, n, arr[i] + 1, n);
pii dw = getder(1, 1, n, 1, arr[i] - 1);
if (up.ff == 0) up.sc = 1;
if (dw.ff == 0) dw.sc = 1;
up.ff++; dw.ff++;
pii now = {up.ff + dw.ff - 1, (up.sc * dw.sc) % inf};
if (now.ff == ans.ff) (ans.sc += now.sc) %= inf;
else if (now.ff > ans.ff) ans = now;
updinc(1, 1, n, arr[i], up);
updder(1, 1, n, arr[i], dw);
} cout << ans.ff << ' ' << (ans.sc * binpow(2, n - ans.ff)) % inf;
}
int32_t main() {
int t = 1;
// cin >> t;
while (t--) {
solve();
cout << endl;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 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 |
2392 KB |
Output is correct |
| 5 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
1 ms |
348 KB |
Output is correct |
| 8 |
Correct |
1 ms |
348 KB |
Output is correct |
| 9 |
Correct |
1 ms |
348 KB |
Output is correct |
| 10 |
Correct |
2 ms |
348 KB |
Output is correct |
| 11 |
Correct |
147 ms |
19376 KB |
Output is correct |
| 12 |
Correct |
123 ms |
21180 KB |
Output is correct |
| 13 |
Correct |
110 ms |
12740 KB |
Output is correct |
| 14 |
Correct |
155 ms |
19132 KB |
Output is correct |
| 15 |
Correct |
206 ms |
21804 KB |
Output is correct |
| 16 |
Correct |
222 ms |
22204 KB |
Output is correct |
| 17 |
Incorrect |
177 ms |
18620 KB |
Output isn't correct |
| 18 |
Incorrect |
172 ms |
18624 KB |
Output isn't correct |
| 19 |
Incorrect |
167 ms |
18628 KB |
Output isn't correct |
| 20 |
Incorrect |
169 ms |
18908 KB |
Output isn't correct |
