Submission #607756

#	Time	Username	Problem	Language	Result	Execution time	Memory
607756		nguyen31hoang08minh2003	Zoltan (COCI16_zoltan)	C++14	140 / 140	214 ms	16232 KiB

zoltan

/*
\-\//\\//\\/-/\-\//\\//\\/-/\-\//\\//\\/-/\-\//\\//\\/-/\-\//\\//\\/-/\-\//\\//\\/-/\-\//\\//\\/-/\-\//\\//\\/-/\-\//\\//\\/-/\-\//\\//\\/-/
\\--\//\\/--//\\--\//\\/--//\\--\//\\/--//\\--\//\\/--//\\--\//\\/--//\\--\//\\/--//\\--\//\\/--//\\--\//\\/--//\\--\//\\/--//\\--\//\\/--//
/|\---\/---/|\/|\---\/---/|\/|\---\/---/|\/|\---\/---/|\/|\---\/---/|\/|\---\/---/|\/|\---\/---/|\/|\---\/---/|\/|\---\/---/|\/|\---\/---/|\
\||\--/\--/||/\||\--/\--/||/\||\--/\--/||/\||\--/\--/||/\||\--/\--/||/\||\--/\--/||/\||\--/\--/||/\||\--/\--/||/\||\--/\--/||/\||\--/\--/||/
/|||\//\\/|||\/|||\//\\/|||\/|||\//\\/|||\/|||\//\\/|||\/|||\//\\/|||\/|||\//\\/|||\/|||\//\\/|||\/|||\//\\/|||\/|||\//\\/|||\/|||\//\\/|||\
\|||/\\//\|||/\|||/\\//\|||/\|||/\\//\|||/\|||/\\//\|||/\|||/\\//\|||/\|||/\\//\|||/\|||/\\//\|||/\|||/\\//\|||/\|||/\\//\|||/\|||/\\//\|||/
/||/--\/--\||\/||/--\/--\||\/||/--\/--\||\/||/--\/--\||\/||/--\/--\||\/||/--\/--\||\/||/--\/--\||\/||/--\/--\||\/||/--\/--\||\/||/--\/--\||\
\|/---/\---\|/\|/---/\---\|/\|/---/\---\|/\|/---/\---\|/\|/---/\---\|/\|/---/\---\|/\|/---/\---\|/\|/---/\---\|/\|/---/\---\|/\|/---/\---\|/
//--/\\//\--\\//--/\\//\--\\//--/\\//\--\\//--/\\//\--\\//--/\\//\--\\//--/\\//\--\\//--/\\//\--\\//--/\\//\--\\//--/\\//\--\\//--/\\//\--\\
/-/\\//\\//\-\/-/\\//\\//\-\/-/\\//\\//\-\/-/\\//\\//\-\/-/\\//\\//\-\/-/\\//\\//\-\/-/\\//\\//\-\/-/\\//\\//\-\/-/\\//\\//\-\/-/\\//\\//\-\
\-\//\\//\\/-/\-\//\\//\\/-/\-\//\\//\\/-/\-\//\\//\\/-/\-\//\\//\\/-/\-\//\\//\\/-/\-\//\\//\\/-/\-\//\\//\\/-/\-\//\\//\\/-/\-\//\\//\\/-/
\\--\//\\/--//\\--\//\\/--//\\--\//\\/--//\\--\//\\/--//\\--\//\\/--//\\--\//\\/--//\\--\//\\/--//\\--\//\\/--//\\--\//\\/--//\\--\//\\/--//
/|\---\/---/|\/|\---\/---/|\/|\---\/---/|\/|\---\/---/|\/|\---\/---/|\/|\---\/---/|\/|\---\/---/|\/|\---\/---/|\/|\---\/---/|\/|\---\/---/|\
\||\--/\--/||/\||\--/\--/||/\||\--/\--/||/\||\--/\--/||/\||\--/\--/||/\||\--/\--/||/\||\--/\--/||/\||\--/\--/||/\||\--/\--/||/\||\--/\--/||/
/|||\//\\/|||\/|||\//\\/|||\/|||\//\\/|||\/|||\//\\/|||\/|||\//\\/|||\/|||\//\\/|||\/|||\//\\/|||\/|||\//\\/|||\/|||\//\\/|||\/|||\//\\/|||\
\|||/\\//\|||/\|||/\\//\|||/\|||/\\//\|||/\|||/\\//\|||/\|||/\\//\|||/\|||/\\//\|||/\|||/\\//\|||/\|||/\\//\|||/\|||/\\//\|||/\|||/\\//\|||/
/||/--\/--\||\/||/--\/--\||\/||/--\/--\||\/||/--\/--\||\/||/--\/--\||\/||/--\/--\||\/||/--\/--\||\/||/--\/--\||\/||/--\/--\||\/||/--\/--\||\
\|/---/\---\|/\|/---/\---\|/\|/---/\---\|/\|/---/\---\|/\|/---/\---\|/\|/---/\---\|/\|/---/\---\|/\|/---/\---\|/\|/---/\---\|/\|/---/\---\|/
//--/\\//\--\\//--/\\//\--\\//--/\\//\--\\//--/\\//\--\\//--/\\//\--\\//--/\\//\--\\//--/\\//\--\\//--/\\//\--\\//--/\\//\--\\//--/\\//\--\\
/-/\\//\\//\-\/-/\\//\\//\-\/-/\\//\\//\-\/-/\\//\\//\-\/-/\\//\\//\-\/-/\\//\\//\-\/-/\\//\\//\-\/-/\\//\\//\-\/-/\\//\\//\-\/-/\\//\\//\-\
*/
#include <bits/stdc++.h>
#define fore(i, a, b) for (int i = (a), i##_last = (b); i < i##_last; ++i)
#define fort(i, a, b) for (int i = (a), i##_last = (b); i <= i##_last; ++i)
#define ford(i, a, b) for (int i = (a), i##_last = (b); i >= i##_last; --i)
#define fi first
#define se second
#define pb push_back
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using namespace std;
using ll = long long;
using ld = long double;

template<class A, class B> bool maxi(A &a, const B &b) {return (a < b) ? (a = b, true):false;};
template<class A, class B> bool mini(A &a, const B &b) {return (a > b) ? (a = b, true):false;};

typedef unsigned long long ull;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;

const int MOD = 1e9 + 7, ninf = 0xc0c0c0c0;


ii operator | (const ii &a, const ii &b) {
    if (a.fi == b.fi)
        return make_pair(a.fi, (a.se + b.se) % MOD);
    return max(a, b);
}

void operator |= (ii &a, const ii &b) {
    if (a.fi == b.fi)
        (a.se += b.se) %= MOD;
    else if (a.fi < b.fi)
        a = b;
}

class SegmentTree {
private:

    int n;
    vii it;

    ii query(int ql, int qr, int i, int l, int r) const {
        if (qr < l || r < ql)
            return ii(ninf, 0);
        if (ql <= l && r <= qr)
            return it[i];
        const int m = l + r >> 1;
        return query(ql, qr, i << 1, l, m) | query(ql, qr, i << 1 | 1, m + 1, r);
    }

    void update(int q, const ii &val, int i, int l, int r) {
        if (q < l || r < q)
            return;
        if (l == r) {
            it[i] |= val;
            return;
        }
        const int m = l + r >> 1;
        update(q, val, i << 1, l, m);
        update(q, val, i << 1 | 1, m + 1, r);
        it[i] = it[i << 1] | it[i << 1 | 1];
    }

public:

    SegmentTree() {};

    void resize(int m) {
        n = m;
        m = n + 5 << 2;
        it.resize(m, make_pair(ninf, 0));
    }

    ii query(int ql, int qr) const {
        return query(ql, qr, 1, 1, n) | make_pair(0, 1);
    }

    void update(int q, const ii &val) {
        update(q, val, 1, 1, n);
    }

};

const int maxN = 2e5 + 5;

int n, m, a[maxN], p[maxN];
SegmentTree x, y;
ii res(ninf, 0);

void input() {
    cin >> n;
    fort(i, 1, n) {
        cin >> a[i];
        p[i] = i;
    }
}

void solve() {
    sort(p + 1, p + 1 + n, [&](const int &x, const int &y) -> bool {
        return a[x] < a[y];
    });
    for (int l = 1, r = 1; r <= n;) {
        for (++m; r <= n && a[p[l]] == a[p[r]]; ++r);
        for (; l < r; ++l)
            a[p[l]] = m;
    }
    x.resize(m);
    y.resize(m);
    ford(i, n, 1) {
        const auto [gx, tx] = x.query(1, a[i] - 1);
        const auto [gy, ty] = y.query(a[i] + 1, m);
        res |= make_pair(gx + 1 + gy, 1LL * tx * ty % MOD);
        x.update(a[i], make_pair(gx + 1, tx));
        y.update(a[i], make_pair(gy + 1, ty));
    }
    fort(_, 1, n - res.fi)
        (res.se <<= 1) %= MOD;
    cout << res.fi << ' ' << res.se << '\n';
}

int main() {
    #ifdef LOCAL
        freopen("input.INP", "r", stdin);
    #endif // LOCAL
    cin.tie(0) -> sync_with_stdio(0);
    cout.tie(0);
    input();
    solve();
    return 0;
}

Compilation message (stderr)

zoltan.cpp: In member function 'ii SegmentTree::query(int, int, int, int, int) const':
zoltan.cpp:74:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   74 |         const int m = l + r >> 1;
      |                       ~~^~~
zoltan.cpp: In member function 'void SegmentTree::update(int, const ii&, int, int, int)':
zoltan.cpp:85:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   85 |         const int m = l + r >> 1;
      |                       ~~^~~
zoltan.cpp: In member function 'void SegmentTree::resize(int)':
zoltan.cpp:97:15: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   97 |         m = n + 5 << 2;
      |             ~~^~~
zoltan.cpp: In function 'void solve()':
zoltan.cpp:137:20: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  137 |         const auto [gx, tx] = x.query(1, a[i] - 1);
      |                    ^
zoltan.cpp:138:20: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  138 |         const auto [gy, ty] = y.query(a[i] + 1, m);
      |                    ^

• Subtask 1: 140 / 140