Submission #1276831

#TimeUsernameProblemLanguageResultExecution timeMemory
1276831flaming_top1Zoltan (COCI16_zoltan)C++20
140 / 140
187 ms18316 KiB
#include <bits/stdc++.h> #define SPED \ ios_base::sync_with_stdio(false); \ cin.tie(0); \ cout.tie(0); #define endl "\n" #define fi first #define se second #define lint long long #define fami signed #define lore main #define freefire freopen const lint INF = 0x1f1f1f1f1f1f1f1f; const lint NEG = 0xE1E1E1E1E1E1E1E1; const lint mod = 1e9 + 7; using namespace std; int n, K; lint a[200005]; lint maxi = -1, cnt; lint binpow(lint x, lint k) { x %= mod; lint r = 1 % mod; while (k) { if (k & 1) r = r * x % mod; x = x * x % mod; k >>= 1; } return r; } struct Seg { pair<lint, lint> seg[800015]; inline pair<lint, lint> combine(pair<lint, lint> L, pair<lint, lint> R) { if (L.fi < 0) return R; if (R.fi < 0) return L; if (L.fi != R.fi) return (L.fi > R.fi ? L : R); return {L.fi, (L.se + R.se) % mod}; } void update(int node, int l, int r, int idx, pair<lint, lint> k) { if (l == r) { seg[node] = combine(seg[node], k); return; } int mid = (l + r) >> 1; if (idx <= mid) update(node << 1, l, mid, idx, k); else update(node << 1 | 1, mid + 1, r, idx, k); seg[node] = combine(seg[node << 1], seg[node << 1 | 1]); } pair<lint, lint> get(int node, int l, int r, int templ, int tempr) { if (templ <= l and r <= tempr) return seg[node]; if (r < templ or tempr < l) return {-1, 0}; // -∞ int mid = (l + r) >> 1; return combine(get(node << 1, l, mid, templ, tempr), get(node << 1 | 1, mid + 1, r, templ, tempr)); } } st1, st2; void compress() { vector<lint> zip(a + 1, a + 1 + n); sort(zip.begin(), zip.end()); zip.erase(unique(zip.begin(), zip.end()), zip.end()); K = (int)zip.size(); for (int i = 1; i <= n; ++i) a[i] = lower_bound(zip.begin(), zip.end(), a[i]) - zip.begin() + 2; } fami lore() { SPED; cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; compress(); for (int i = n; i >= 1; i--) { auto lis = st1.get(1, 1, 200003, a[i] + 1, 200003); if (lis.fi == 0 and lis.se == 0) lis = {0, 1}; auto lds = st2.get(1, 1, 200003, 1, a[i] - 1); if (lds.fi == 0 and lds.se == 0) lds = {0, 1}; lint len = lis.fi + lds.fi + 1; lint ways = (lis.se * lds.se) % mod; if (len > maxi) { maxi = len; cnt = ways; } else if (len == maxi) { cnt += ways; cnt %= mod; } st1.update(1, 1, 200003, a[i], {lis.fi + 1, lis.se}); st2.update(1, 1, 200003, a[i], {lds.fi + 1, lds.se}); } cnt = cnt % mod * binpow(2, n - maxi) % mod; cout << maxi << " " << cnt << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...