Submission #243537

#TimeUsernameProblemLanguageResultExecution timeMemory
243537VEGAnnZoltan (COCI16_zoltan)C++14
63 / 140
129 ms5920 KiB
#include <bits/stdc++.h> #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; typedef long long ll; const int N = 200100; const int oo = 2e9; const int md = int(1e9) + 7; i2 ans, st[2][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){ i2 res = {0, 0}; for (; v >= 0; v = (v & (v + 1)) - 1) upd(res, st[tp][v]); return res; } void update(int tp, int v, i2 vl){ for (; v < sz(vc); v = (v | (v + 1))) upd(st[tp][v], vl); } 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]; SUM(po[i], po[i - 1]); } for (int i = n - 1; i >= 0; i--){ i2 men = get(0, a[i] - 1); i2 mex = get(1, sz(vc) - a[i] - 2); 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; ll cnt = (ll(po[i + inv]) * ll(mex[1])) % md; (cnt *= men[1]) % md; i2 cur = {len, cnt}; upd(ans, cur); men[0]++; mex[0]++; update(0, a[i], men); update(1, sz(vc) - 1 - a[i], mex); } cout << ans[0] << " " << ans[1]; return 0; }

Compilation message (stderr)

zoltan.cpp: In function 'int main()':
zoltan.cpp:87:25: warning: value computed is not used [-Wunused-value]
         (cnt *= men[1]) % md;
         ~~~~~~~~~~~~~~~~^~~~
zoltan.cpp:89:27: warning: narrowing conversion of 'cnt' from 'll {aka long long int}' to 'int' inside { } [-Wnarrowing]
         i2 cur = {len, cnt};
                           ^
#Verdict Execution timeMemoryGrader output
Fetching results...