oj.uz

Submission #1108892

# Submission time Handle Problem Language Result Execution time Memory
1108892 2024-11-05T15:38:12 Z windowwife Zoltan (COCI16_zoltan) C++14
140 / 140
 497 ms 17912 KB 
#include <bits/stdc++.h>
#define ll long long
#define task ""
using namespace std;
const int maxn = 1e6 + 2, mod = 1e9 + 7;
int n, a[maxn], b[maxn], id, mx = 0, cnt = 0, mx2 = 0, cnt2 = 0;
vector<int> v;
pair<int, int> res[maxn], st[4*maxn];
pair<int, int> merge (pair<int, int> a, pair<int, int> b)
{
    if (a.first == 0 && b.first == 0) return {0, 1};
    if (a < b) swap(a, b);
    if (a.first == b.first)
    {
        a.second += b.second;
        if (a.second >= mod) a.second -= mod;
    }
    return a;
}
void build (int node, int l, int r)
{
    if (l == r)
    {
        st[node] = {0, 1};
        return;
    }
    int mid = (l + r)/2;
    build(2*node, l, mid);
    build(2*node + 1, mid + 1, r);
    st[node] = merge(st[2*node], st[2*node + 1]);
}
void update (int node, int l, int r, int idx, pair<int, int> res)
{
    if (l == r)
    {
        st[node] = merge(st[node], res);
        return;
    }
    int mid = (l + r)/2;
    if (idx <= mid) update(2*node, l, mid, idx, res);
    else update(2*node + 1, mid + 1, r, idx, res);
    st[node] = merge(st[2*node], st[2*node + 1]);
}
pair<int, int> get (int node, int l, int r, int cl, int cr)
{
    if (cl > cr) return {0, 1};
    if (r < cl || cr < l) return {-1, 0};
    if (cl <= l && r <= cr) return st[node];
    int mid = (l + r)/2;
    return merge(get(2*node, l, mid, cl, cr), get(2*node + 1, mid + 1, r, cl, cr));
}
int p (int ok)
{
    ll res = 1, a = 2;
    for (; ok > 0; ok >>= 1)
    {
        if (ok & 1) res = res * a % mod;
        a = a * a % mod;
    }
    return res;
}
int main()
{
    //freopen(task".INP", "r", stdin);
    //freopen(task".OUT", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        v.push_back(a[i]);
        b[n - i + 1] = b[n + i - 1] = a[i];
    }
    sort(v.begin(), v.end());
    v.resize(unique(v.begin(), v.end()) - v.begin());
    build(1, 1, n);
    for (int i = 1; i <= 2*n - 1; i++)
    {
        id = upper_bound(v.begin(), v.end(), b[i]) - v.begin();
        res[i] = get(1, 1, n, 1, id - 1);
        res[i].first++;
        update(1, 1, n, id, res[i]);
        if (mx < res[i].first)
        {
            mx = res[i].first;
            cnt = res[i].second;
        }
        else if (mx == res[i].first)
        {
            cnt += res[i].second;
            if (cnt >= mod) cnt -= mod;
        }
    }
    build(1, 1, n);
    for (int i = 1; i <= 2*n - 1; i++)
    {
        if (i == n) continue;
        id = upper_bound(v.begin(), v.end(), b[i]) - v.begin();
        res[i] = get(1, 1, n, 1, id - 1);
        res[i].first++;
        update(1, 1, n, id, res[i]);
        if (mx2 < res[i].first)
        {
            mx2 = res[i].first;
            cnt2 = res[i].second;
        }
        else if (mx2 == res[i].first)
        {
            cnt2 += res[i].second;
            if (cnt2 >= mod) cnt2 -= mod;
        }
    }
    if (mx > mx2) cout << mx << " " << 1LL*cnt*p(n - mx)%mod;
    else cout << mx << " " << (1LL*(cnt - cnt2)*p(n - mx)%mod + 1LL*cnt2*p(n - mx - 1)%mod)%mod;
}

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6480 KB Output is correct
2 Correct 2 ms 6480 KB Output is correct
3 Correct 1 ms 6480 KB Output is correct
4 Correct 1 ms 6480 KB Output is correct
5 Correct 1 ms 6480 KB Output is correct
6 Correct 1 ms 6480 KB Output is correct
7 Correct 2 ms 6480 KB Output is correct
8 Correct 3 ms 6480 KB Output is correct
9 Correct 2 ms 6644 KB Output is correct
10 Correct 3 ms 6480 KB Output is correct
11 Correct 262 ms 17544 KB Output is correct
12 Correct 237 ms 17604 KB Output is correct
13 Correct 222 ms 15560 KB Output is correct
14 Correct 320 ms 17604 KB Output is correct
15 Correct 454 ms 17848 KB Output is correct
16 Correct 497 ms 17912 KB Output is correct
17 Correct 355 ms 17860 KB Output is correct
18 Correct 322 ms 17708 KB Output is correct
19 Correct 311 ms 17864 KB Output is correct
20 Correct 322 ms 17788 KB Output is correct