Submission #1114263

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114263		ljtunas	Zoltan (COCI16_zoltan)	C++14	140 / 140	105 ms	17780 KiB

zoltan

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define fi first
#define se second
#define Rep(i, n)  for(int i = 1; i <= n; ++i)
#define For(i, a, b) for(int i = a; i <= b; ++i)
#define Ford(i, a, b) for(int i = a; i >= b; --i)
#define Forv(v, h) for(auto &v : h)
#define Bit(x, i) ((x) >> (i) & 1ll)
#define onbit(x, i) ((x)  (1ll << i))
#define offbit(x, i) ((x) &~ (1ll << i))
#define cnt_bit(x) __builtin_popcountll(x)
#define Log2(x) (63 - __builtin_clzll(x))
#define all(h) h.begin(), h.end()
#define reset(h, v) (memset(h, v, sizeof(h)))
#define memoryof(v) (sizeof(v) / 1024 / 1024)

using ii  = pair<int, int>;
using ull = unsigned long long;
using db  = long double;
using vi  = vector<int>;
using vvi  = vector<vi>;
using vii  = vector<ii>;

const int dx[] = {0, 0, +1, -1};
const int dy[] = {-1, +1, 0, 0};
const int MAXN = 2e5  + 10;
const int  MOD = 1e9  + 7;
const int   oo = 1e18 + 1;
const int base = 311;

template <class X, class Y> bool maximize(X &a, const Y &b) {
    if(a < b) return a = b, true;
    return false;
}

//template <class X, class Y> bool minimize(X &a, const Y &b) {
//    if(a > b) return a = b, true;
//    return false;
//}

// (x, y) -> (u, v) = Ckn(u - x, x + y - u - v);
// Ckn(k, a) * Ckn(k, b) = C(a, a + b);  (k : 1 -> min(a, b))

void fixmod(int &val) {
    if (val < 0) val += MOD*MOD;
    val %= MOD;
}

int Pow(int a, int n) {
    int res = 1;
    while (n > 0) {
        if (n & 1) res = (res * a) % MOD;
        a = (a * a) % MOD, n >>= 1;
    }
    return res;
}

int n;

void combine(ii & x, const ii& y) {
    if (x.fi == y.fi) x.se += y.se, fixmod(x.se);
    else if (x.fi < y.fi) {
        x = y;
    }
}

struct fenwick {
    ii bit[2][MAXN];
    void upd(bool t, int u, ii val)
    {
        if (!t) for (; u <= n; u += u&-u) combine(bit[t][u], val);
        else for (; u; u -= u&-u) combine(bit[t][u], val);
    }
    ii get(bool t, int u)
    {
        ii res = {0, 0};
        if (t) for (; u <= n; u += u&-u) combine(res, bit[t][u]);
        else for (; u; u -= u&-u) combine(res, bit[t][u]);
        return res;
    }
} ac;

void Progess() {
    cin >> n;
    vector <int> a(n);
    For (i, 0, n - 1) cin >> a[i];
    vector<int> vct = a; sort(all(vct));
    For (i, 0, n - 1) {
        a[i] = lower_bound(all(vct), a[i]) - vct.begin() + 1;
    }
    vector <ii> lis(n), lds(n);
    Ford (i, n - 1, 0) {
        lis[i] = ac.get(0, a[i] - 1);
        if (lis[i].fi == 0) {
            lis[i] = {0, 1};
            ac.upd(0, a[i], {1, 1});
        } else {
            ac.upd(0, a[i], {lis[i].fi + 1, lis[i].se});
        }

        lds[i] = ac.get(1, a[i] + 1);
        if (lds[i].fi == 0) {
            lds[i] = {0, 1};
            ac.upd(1, a[i], {1, 1});
        } else {
            ac.upd(1, a[i], {lds[i].fi + 1, lds[i].se});
        }
//        cerr << lis[i].fi << ' ' << lds[i].fi << '\n';
    }

    ii res = {0, 0};
    For (i, 0, n - 1) combine(res, {lis[i].fi + lds[i].fi + 1, (lis[i].se * lds[i].se) % MOD});
    int ans = (res.se * Pow(2, n - res.fi)) % MOD;
    cout << res.fi << ' ' << ans << '\n';
}

signed main(void) {
    ios_base::sync_with_stdio(false);cin.tie(nullptr);
    cout.tie(nullptr);

    #define task "zoltan"
    if (fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }//_______________________________
    Progess();
    cerr << "\nTime elapsed: " << (1.0 * clock() / CLOCKS_PER_SEC) << " s.\n";
    return (0 ^ 0);
}

Compilation message (stderr)

zoltan.cpp: In function 'int main()':
zoltan.cpp:127:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  127 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
zoltan.cpp:128:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  128 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 140 / 140