Submission #140609

#TimeUsernameProblemLanguageResultExecution timeMemory
140609MinnakhmetovZoltan (COCI16_zoltan)C++14
140 / 140
339 ms9896 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long #define all(aaa) aaa.begin(), aaa.end() const int MOD = 1e9 + 7; struct Node { int val, w; }; Node operator + (Node a, Node b) { if (a.val == b.val) { if (a.val == 0) return { 0, 1 }; Node c = { a.val, a.w + b.w }; if (c.w >= MOD) c.w -= MOD; return c; } if (a.val > b.val) return a; return b; } const int N = 2e5 + 5; Node t[N * 4], mxr[N]; vector<int> vd; int a[N]; int n; void upd(int x, Node y, int v = 1, int L = 0, int R = vd.size() - 1) { if (L == R) { t[v] = t[v] + y; } else { int m = (L + R) >> 1; if (x <= m) upd(x, y, v * 2, L, m); else upd(x, y, v * 2 + 1, m + 1, R); t[v] = t[v * 2] + t[v * 2 + 1]; } } Node que(int l, int r, int v = 1, int L = 0, int R = vd.size() - 1) { if (l > r) return { 0, 1 }; if (l == L && r == R) { return t[v]; } int m = (L + R) >> 1; return que(l, min(m, r), v * 2, L, m) + que(max(m + 1, l), r, v * 2 + 1, m + 1, R); } void brute() { Node ans = { 0, 1 }; deque<int> q; for (int i = 0; i < (1 << (n - 1)); i++) { q = { a[0] }; for (int j = 1; j < n; j++) { if ((i >> (j - 1)) & 1) q.push_back(a[j]); else q.push_front(a[j]); } fill(t, t + vd.size() * 4, (Node){ 0, 1 }); Node cur = { 0, 1 }; for (int j = 0; j < n; j++) { Node res = que(0, q[j] - 1); res.val++; upd(q[j], res); ans = ans + res; cur = cur + res; } } cout << ans.val << " " << ans.w << "\n"; } signed main() { #ifdef HOME freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif ios_base::sync_with_stdio(0); cin.tie(0); cin >> n; mt19937 rnd(time(0)); for (int i = 0; i < n; i++) { cin >> a[i]; vd.push_back(a[i]); } sort(all(vd)); vd.erase(unique(all(vd)), vd.end()); for (int i = 0; i < n; i++) { a[i] = lower_bound(all(vd), a[i]) - vd.begin(); } fill(t, t + N * 4, (Node){ 0, 1 }); for (int i = n - 1; i >= 0; i--) { Node res = que(a[i] + 1, vd.size() - 1); res.val++; upd(a[i], res); mxr[i] = res; } fill(t, t + N * 4, (Node){ 0, 1 }); for (int i = n - 1; i > 0; i--) { Node res = que(0, a[i] - 1); res.val++; upd(a[i], res); } Node mx_subseq = { 0, 1 }, mx_subseq_with_first = { 0, 0 }; for (int i = 0; i < n; i++) { Node cur = que(0, a[i] - 1); cur.val += mxr[i].val; cur.w = cur.w * (ll)mxr[i].w % MOD; // cout << "! " << cur.val << " " << cur.w << "\n"; // cout << "! " << mxr[i].val << " " << mxr[i].w << "\n"; if (i == 0) mx_subseq_with_first = cur; else mx_subseq = mx_subseq + cur; } // cout << "!" << mx_subseq.val << " " << mx_subseq.w << "\n"; // cout << mx_subseq_with_first.val << " " << mx_subseq_with_first.w << "\n"; // for (int i = 0; i < n; i++) { // cout << mxr[i].val << " " << mxr[i].w << "\n"; // } // cout << "\n"; for (int i = 0; i < n - 1 - (mx_subseq.val > 1 ? mx_subseq.val : 0); i++) { mx_subseq.w = mx_subseq.w * 2 % MOD; } for (int i = 0; i < n - mx_subseq_with_first.val; i++) { mx_subseq_with_first.w = mx_subseq_with_first.w * 2 % MOD; } Node ans = mx_subseq + mx_subseq_with_first; cout << ans.val << " " << ans.w; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...