oj.uz

Submission #607756

# Submission time Handle Problem Language Result Execution time Memory
607756 2022-07-27T03:01:12 Z nguyen31hoang08minh2003 Zoltan (COCI16_zoltan) C++14
140 / 140
 214 ms 16232 KB 
/*
\-\//\\//\\/-/\-\//\\//\\/-/\-\//\\//\\/-/\-\//\\//\\/-/\-\//\\//\\/-/\-\//\\//\\/-/\-\//\\//\\/-/\-\//\\//\\/-/\-\//\\//\\/-/\-\//\\//\\/-/
\\--\//\\/--//\\--\//\\/--//\\--\//\\/--//\\--\//\\/--//\\--\//\\/--//\\--\//\\/--//\\--\//\\/--//\\--\//\\/--//\\--\//\\/--//\\--\//\\/--//
/|\---\/---/|\/|\---\/---/|\/|\---\/---/|\/|\---\/---/|\/|\---\/---/|\/|\---\/---/|\/|\---\/---/|\/|\---\/---/|\/|\---\/---/|\/|\---\/---/|\
\||\--/\--/||/\||\--/\--/||/\||\--/\--/||/\||\--/\--/||/\||\--/\--/||/\||\--/\--/||/\||\--/\--/||/\||\--/\--/||/\||\--/\--/||/\||\--/\--/||/
/|||\//\\/|||\/|||\//\\/|||\/|||\//\\/|||\/|||\//\\/|||\/|||\//\\/|||\/|||\//\\/|||\/|||\//\\/|||\/|||\//\\/|||\/|||\//\\/|||\/|||\//\\/|||\
\|||/\\//\|||/\|||/\\//\|||/\|||/\\//\|||/\|||/\\//\|||/\|||/\\//\|||/\|||/\\//\|||/\|||/\\//\|||/\|||/\\//\|||/\|||/\\//\|||/\|||/\\//\|||/
/||/--\/--\||\/||/--\/--\||\/||/--\/--\||\/||/--\/--\||\/||/--\/--\||\/||/--\/--\||\/||/--\/--\||\/||/--\/--\||\/||/--\/--\||\/||/--\/--\||\
\|/---/\---\|/\|/---/\---\|/\|/---/\---\|/\|/---/\---\|/\|/---/\---\|/\|/---/\---\|/\|/---/\---\|/\|/---/\---\|/\|/---/\---\|/\|/---/\---\|/
//--/\\//\--\\//--/\\//\--\\//--/\\//\--\\//--/\\//\--\\//--/\\//\--\\//--/\\//\--\\//--/\\//\--\\//--/\\//\--\\//--/\\//\--\\//--/\\//\--\\
/-/\\//\\//\-\/-/\\//\\//\-\/-/\\//\\//\-\/-/\\//\\//\-\/-/\\//\\//\-\/-/\\//\\//\-\/-/\\//\\//\-\/-/\\//\\//\-\/-/\\//\\//\-\/-/\\//\\//\-\
\-\//\\//\\/-/\-\//\\//\\/-/\-\//\\//\\/-/\-\//\\//\\/-/\-\//\\//\\/-/\-\//\\//\\/-/\-\//\\//\\/-/\-\//\\//\\/-/\-\//\\//\\/-/\-\//\\//\\/-/
\\--\//\\/--//\\--\//\\/--//\\--\//\\/--//\\--\//\\/--//\\--\//\\/--//\\--\//\\/--//\\--\//\\/--//\\--\//\\/--//\\--\//\\/--//\\--\//\\/--//
/|\---\/---/|\/|\---\/---/|\/|\---\/---/|\/|\---\/---/|\/|\---\/---/|\/|\---\/---/|\/|\---\/---/|\/|\---\/---/|\/|\---\/---/|\/|\---\/---/|\
\||\--/\--/||/\||\--/\--/||/\||\--/\--/||/\||\--/\--/||/\||\--/\--/||/\||\--/\--/||/\||\--/\--/||/\||\--/\--/||/\||\--/\--/||/\||\--/\--/||/
/|||\//\\/|||\/|||\//\\/|||\/|||\//\\/|||\/|||\//\\/|||\/|||\//\\/|||\/|||\//\\/|||\/|||\//\\/|||\/|||\//\\/|||\/|||\//\\/|||\/|||\//\\/|||\
\|||/\\//\|||/\|||/\\//\|||/\|||/\\//\|||/\|||/\\//\|||/\|||/\\//\|||/\|||/\\//\|||/\|||/\\//\|||/\|||/\\//\|||/\|||/\\//\|||/\|||/\\//\|||/
/||/--\/--\||\/||/--\/--\||\/||/--\/--\||\/||/--\/--\||\/||/--\/--\||\/||/--\/--\||\/||/--\/--\||\/||/--\/--\||\/||/--\/--\||\/||/--\/--\||\
\|/---/\---\|/\|/---/\---\|/\|/---/\---\|/\|/---/\---\|/\|/---/\---\|/\|/---/\---\|/\|/---/\---\|/\|/---/\---\|/\|/---/\---\|/\|/---/\---\|/
//--/\\//\--\\//--/\\//\--\\//--/\\//\--\\//--/\\//\--\\//--/\\//\--\\//--/\\//\--\\//--/\\//\--\\//--/\\//\--\\//--/\\//\--\\//--/\\//\--\\
/-/\\//\\//\-\/-/\\//\\//\-\/-/\\//\\//\-\/-/\\//\\//\-\/-/\\//\\//\-\/-/\\//\\//\-\/-/\\//\\//\-\/-/\\//\\//\-\/-/\\//\\//\-\/-/\\//\\//\-\
*/
#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

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.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 121 ms 12672 KB Output is correct
12 Correct 100 ms 11088 KB Output is correct
13 Correct 97 ms 10420 KB Output is correct
14 Correct 134 ms 11372 KB Output is correct
15 Correct 191 ms 14052 KB Output is correct
16 Correct 214 ms 16232 KB Output is correct
17 Correct 162 ms 13536 KB Output is correct
18 Correct 151 ms 13616 KB Output is correct
19 Correct 153 ms 13632 KB Output is correct
20 Correct 156 ms 13564 KB Output is correct