Submission #519212

#TimeUsernameProblemLanguageResultExecution timeMemory
519212XIIZoltan (COCI16_zoltan)C++17
21 / 140
260 ms10124 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; #define fi first #define se second #define mp make_pair #define eb emplace_back #define ALL(x) (x).begin(), (x).end() #define FOR(i, a, b) for(int i = (a); i < (b); ++i) #define FORU(i, a, b) for(int i = (a); i <= (b); ++i) #define FORD(i, a, b) for(int i = (a); i >= (b); --i) #define IOS cin.tie(0)->sync_with_stdio(false); #define PROB "COCI16_zoltan" void Fi(){ if(fopen(PROB".inp", "r")){ freopen(PROB".inp", "r", stdin); freopen(PROB".out", "w", stdout); } } const int N = 2e5 + 1; const int MOD = 1e9 + 7; int a[N], n; vector<int> X; using pi = pair<int, int>; pi comb(const pi &a, const pi &b){ return a.fi == b.fi ? mp(a.fi, (a.se + b.se) % MOD) : (a.fi > b.fi) ? a : b; } int lz[N * 4]; pi ST[N * 4]; int mul(const int &a, const int &b){ return (1LL * a * b) % MOD; } void down(int id){ ST[id * 2].se = mul(ST[id * 2].se, lz[id]); ST[id * 2 + 1].se = mul(ST[id * 2 + 1].se, lz[id]); lz[id * 2] = mul(lz[id * 2], lz[id]); lz[id * 2 + 1] = mul(lz[id * 2 + 1], lz[id]); lz[id] = 1; } void update(const int &i, const pi &v, int id = 1, int be = 1, int en = X.size()){ if(be == en){ ST[id] = comb(ST[id], v); return; } int mi = (be + en) / 2; if(lz[id] > 1) down(id); if(i <= mi) update(i, v, id * 2, be, mi); else update(i, v, id * 2 + 1, mi + 1, en); ST[id] = comb(ST[id * 2], ST[id * 2 + 1]); } void updateChoice(){ ST[1].se = (ST[1].se * 2) % MOD; lz[1] = (lz[1] * 2) % MOD; } pi query(const int &l, const int &r, int id = 1, int be = 1, int en = X.size()){ if(r < be || en < l) return {0, 0}; if(l <= be && en <= r) return ST[id]; int mi = (be + en) / 2; if(lz[id] > 1) down(id); return comb(query(l, r, id * 2, be, mi), query(l, r, id * 2 + 1, mi + 1, en)); } int p2[N]; void init(){ p2[0] = 1; FORU(i, 1, n) p2[i] = (p2[i - 1] * 2) % MOD; } int main(){ IOS; Fi(); cin >> n; init(); FORU(i, 1, n){ cin >> a[i]; X.eb(a[i]); } memset(lz, 1, sizeof(lz)); sort(ALL(X)); X.resize(unique(ALL(X)) - X.begin()); pi ans = {0, 0}; FORU(i, 1, n){ a[i] = lower_bound(ALL(X), a[i]) - X.begin() + 1; pi lef = query(a[i] + 1, X.size()); lef.fi += 1; pi rig = query(1, a[i] - 1); rig.fi += 1; updateChoice(); pi tmp = comb({1, p2[i - 1]}, comb(lef, rig)); update(a[i], tmp); tmp.se = mul(tmp.se, p2[n - i]); ans = comb(ans, tmp); } cout << ans.fi << " " << ans.se; return 0; }

Compilation message (stderr)

zoltan.cpp: In function 'void Fi()':
zoltan.cpp:20:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |         freopen(PROB".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
zoltan.cpp:21:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |         freopen(PROB".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...