Submission #198156

#TimeUsernameProblemLanguageResultExecution timeMemory
198156mkisicZoltan (COCI16_zoltan)C++14
56 / 140
459 ms13176 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef double lf; typedef long double Lf; typedef pair <int,int> pii; typedef pair <ll, ll> pll; #define TRACE(x) cerr << #x << " " << x << endl #define FOR(i, a, b) for (int i = (a); i < int(b); i++) #define REP(i, n) FOR(i, 0, n) #define all(x) (x).begin(), (x).end() #define _ << " " << #define fi first #define sec second #define mp make_pair #define pb push_back const int MAXN = 200100; const int offset = (1 << 18); const int MOD = 1e9 + 7; int add(int a, int b) { a += b; if (a >= MOD) a -= MOD; if (a < 0) a += MOD; return a; } int mul(int a, int b) { return (ll)a * b % MOD; } struct tournament { pii p[offset * 2]; tournament() { REP(i, offset * 2) p[i] = {0, 0}; } pii merge(pii a, pii b) { if (a.fi > b.fi) return a; if (b.fi > a.fi) return b; return {a.fi, add(a.sec, b.sec)}; } void update(int a, pii b) { a += offset; p[a] = merge(p[a], b); a /= 2; while (a) { p[a] = merge(p[a * 2], p[a * 2 + 1]); a /= 2; } } pii get(int cvor, int l, int r, int a, int b) { if (l > b || r < a || l > r) return {0, 0}; if (l >= a && r <= b) return p[cvor]; int mid = (l + r) / 2; pii x = get(cvor * 2, l, mid, a, b); pii y = get(cvor * 2 + 1, mid + 1, r, a, b); return merge(x, y); } void clear() { REP(i, offset * 2) p[i] = {0, 0}; } }; tournament T; int n; vector <int> saz; vector <pii> pt, pt1; int pot[MAXN]; int main() { pot[0] = 1; FOR(i, 1, MAXN) pot[i] = mul(2, pot[i - 1]); scanf("%d",&n); REP(i, n) { int x; scanf("%d",&x); saz.pb(x); if (i) pt.pb({-(i + 1), x}); pt.pb({i + 1, x}); pt1.pb({i + 1, x}); } sort(all(saz)); saz.erase(unique(all(saz)), saz.end()); sort(all(pt)); pii ans, ans1; REP(i, (int)pt.size()) { pt[i].sec = lower_bound(all(saz), pt[i].sec) - saz.begin(); pii t = T.get(1, 0, offset - 1, 0, pt[i].sec - 1); if (t.fi == 0) t.sec = 1; t.fi++; ans = T.merge(ans, t); T.update(pt[i].sec, t); } T.clear(); pt = pt1; REP(i, (int)pt.size()) { pt[i].sec = lower_bound(all(saz), pt[i].sec) - saz.begin(); pii t = T.get(1, 0, offset - 1, 0, pt[i].sec - 1); if (t.fi == 0) t.sec = 1; t.fi++; ans1 = T.merge(ans1, t); T.update(pt[i].sec, t); } int sol = ans.sec; //if (ans1.fi == ans.fi) sol = add(sol, -ans1.sec); if (ans.fi == 1) sol = n; printf("%d %d\n",ans.fi, mul(sol, pot[n - ans.fi])); return 0; }

Compilation message (stderr)

zoltan.cpp: In function 'int main()':
zoltan.cpp:86:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&n);
   ~~~~~^~~~~~~~~
zoltan.cpp:89:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&x);
     ~~~~~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...