Submission #243523

#TimeUsernameProblemLanguageResultExecution timeMemory
243523VEGAnnZoltan (COCI16_zoltan)C++14
140 / 140
388 ms11096 KiB
#include <bits/stdc++.h> //#pragma GCC optimize("unroll-loops") //#pragma GCC optimize("-O3") //#pragma GCC optimize("Ofast") //#pragma GCC optimize("fast-math") //#pragma GCC optimize("no-stack-protector") #define all(x) x.begin(),x.end() #define sz(x) ((int)x.size()) #define i2 array<int,2> #define PB push_back using namespace std; const int N = 200100; const int oo = 2e9; const int md = int(1e9) + 7; i2 ans, st[2][4 * N]; vector<int> vc; int n, a[N], po[N]; int mult(int x, int y) { return (1ll * x * y) % md; } void SUM(int &x, int y){ x += y; if (x >= md) x -= md; } void upd(i2 &cr, i2 nw){ if (nw[0] > cr[0]) cr = nw; else if (nw[0] == cr[0]){ SUM(cr[1], nw[1]); } } i2 get(int tp, int v, int tl, int tr, int l, int r){ if (l > r) return {0, 0}; if (tl == l && tr == r) return st[tp][v]; int md = (tl + tr) >> 1; i2 res = get(tp, v + v, tl, md, l, min(r, md)); upd(res, get(tp, v + v + 1, md + 1, tr, max(md + 1, l), r)); return res; } void update(int tp, int v, int l, int r, int ps, i2 vl){ if (l == r){ upd(st[tp][v], vl); return; } int md = (l + r) >> 1; if (ps <= md) update(tp, v + v, l, md, ps, vl); else update(tp, v + v + 1, md + 1 ,r, ps, vl); st[tp][v] = st[tp][v + v]; upd(st[tp][v], st[tp][v + v + 1]); } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); #ifdef _LOCAL freopen("in.txt","r",stdin); #endif // _LOCAL cin >> n; for (int i = 0; i < n; i++) { cin >> a[i]; vc.PB(a[i]); } sort(all(vc)); vc.resize(unique(all(vc)) - vc.begin()); for (int i = 0; i < n; i++) a[i] = lower_bound(all(vc), a[i]) - vc.begin(); po[0] = 1; for (int i = 1; i <= n; i++) po[i] = (po[i - 1] * 2) % md; for (int i = n - 1; i >= 0; i--){ i2 men = get(0, 1, 0, sz(vc) - 1, 0, a[i] - 1); i2 mex = get(1, 1, 0, sz(vc) - 1, a[i] + 1, sz(vc) - 1); if (men[0] == 0) men[1] = 1; if (mex[0] == 0) mex[1] = 1; int len = men[0] + mex[0] + 1; int inv = (n - i) - len; i2 cur = {len, mult(po[i + inv], mult(mex[1], men[1]))}; upd(ans, cur); // cerr << ans[0] << " " << ans[1] << '\n'; men[0]++; mex[0]++; update(0, 1, 0, sz(vc) - 1, a[i], men); update(1, 1, 0, sz(vc) - 1, a[i], mex); } cout << ans[0] << " " << ans[1]; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...