Submission #864470

#TimeUsernameProblemLanguageResultExecution timeMemory
864470NeroZeinZoltan (COCI16_zoltan)C++17
98 / 140
274 ms18260 KiB
#include "bits/stdc++.h" using namespace std; #ifdef Nero #include "Deb.h" #else #define deb(...) #endif const int N = 2e5 + 5; const int md = (int) 1e9 + 7; int a[N], p2[N]; pair<int, int> seg[N * 2]; pair<int, int> lis[N], lds[N]; void add(int& x, int y) { x += y; if (x >= md) x -= md; } int mul(int x, int y) { return (int) ((long long) x * y % md); } pair<int, int> comb(pair<int,int> x, pair<int,int> y) { if (x.first == y.first) { return {x.first, x.second + y.second}; } return max(x, y); } void upd(int nd, int l, int r, int p, pair<int, int> v) { if (l == r) { seg[nd] = v; return; } int mid = (l + r) >> 1; int rs = nd + ((mid - l + 1) << 1); if (p <= mid) { upd(nd + 1, l, mid, p, v); } else { upd(rs, mid + 1, r, p, v); } seg[nd] = comb(seg[nd + 1], seg[rs]); } pair<int, int> qry(int nd, int l, int r, int s, int e) { if (l >= s && r <= e) { return seg[nd]; } int mid = (l + r) >> 1; int rs = nd + ((mid - l + 1) << 1); if (mid >= e) { return qry(nd + 1, l, mid, s, e); } else { if (mid < s) { return qry(rs, mid + 1, r, s, e); } else { return comb(qry(nd + 1, l, mid, s, e), qry(rs, mid + 1, r, s, e)); } } } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); p2[0] = 1; for (int i = 1; i < N; ++i) { p2[i] = mul(p2[i - 1], 2); } int n; cin >> n; map<int, int> mp; for (int i = 0; i < n; ++i) { cin >> a[i]; mp[a[i]]; } int cnt = 0; for (auto& it : mp) { it.second = cnt++; } for (int i = 0; i < n; ++i) { a[i] = mp[a[i]]; } vector<int> id(n); iota(id.begin(), id.end(), 0); sort(id.begin(), id.end(), [&](int i, int j) { return a[i] == a[j] ? i < j : a[i] > a[j]; }); upd(0, 0, n, n, {0, 1}); for (int i = 0; i < n; ++i) { int ind = id[i]; lis[ind] = qry(0, 0, n, ind, n); lis[ind].first++; upd(0, 0, n, ind, lis[ind]); } for (int i = 0; i < N * 2; ++i) { seg[i] = {0, 0}; } sort(id.begin(), id.end(), [&](int i, int j) { return a[i] == a[j] ? i < j : a[i] < a[j]; }); int mx = 1; upd(0, 0, n, n, {0, 1}); for (int i = 0; i < n; ++i) { int ind = id[i]; lds[ind] = qry(0, 0, n, ind, n); lds[ind].first++; upd(0, 0, n, ind, lds[ind]); mx = max(mx, lis[ind].first + lds[ind].first - 1); } cnt = 0; for (int i = 0; i < n; ++i) { if (lis[i].first + lds[i].first == mx + 1) { add(cnt, mul(p2[n - mx], mul(lds[i].second, lis[i].second))); } } cout << mx << ' ' << cnt << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...