| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 996903 |
2024-06-11T12:04:19 Z |
otarius |
Zoltan (COCI16_zoltan) |
C++17 |
|
247 ms |
19904 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[1000040], der[1000040];
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) {
if (inc[v].ff < val.ff)
inc[v] = val;
else if (inc[v].ff == val.ff)
inc[v].sc += val.sc;
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) {
if (der[v].ff < val.ff)
der[v] = val;
else if (der[v].ff == val.ff)
der[v].sc += val.sc;
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) {
ll res = 1; a %= inf;
while (b) {
if (b & 1) {
res = res * a % inf;
} a = a * a % inf;
b /= 2;
} return res;
}
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);
} ans.sc %= inf;
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 |
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 |
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 |
1 ms |
348 KB |
Output is correct |
| 11 |
Correct |
141 ms |
19392 KB |
Output is correct |
| 12 |
Correct |
122 ms |
18876 KB |
Output is correct |
| 13 |
Correct |
111 ms |
10696 KB |
Output is correct |
| 14 |
Correct |
181 ms |
19056 KB |
Output is correct |
| 15 |
Correct |
206 ms |
19644 KB |
Output is correct |
| 16 |
Correct |
247 ms |
19904 KB |
Output is correct |
| 17 |
Correct |
189 ms |
17852 KB |
Output is correct |
| 18 |
Correct |
181 ms |
17596 KB |
Output is correct |
| 19 |
Correct |
175 ms |
17596 KB |
Output is correct |
| 20 |
Correct |
170 ms |
17596 KB |
Output is correct |
