Submission #1268087

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268087		MisterReaper	Zoltan (COCI16_zoltan)	C++20	105 / 140	137 ms	8280 KiB

zoltan

// File A.cpp created on 07.09.2025 at 23:55:34
#include <bits/stdc++.h>

using i64 = long long;

#ifdef DEBUG 
    #include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
    #define debug(...) void(23)
#endif

template<typename T>
T power(T a, i64 b) {
    T res {1};
    while (b) {
        if (b & 1) {
            res *= a;
        }
        a *= a;
        b >>= 1;
    }
    return res;
}

constexpr int md = int(1E9) + 7;
struct MInt {
    int val;
    MInt() : val(0) {}
    template<typename T>
    MInt(T x) {
        if (-md <= x && x < md) {
            val = int(x);
        } else {
            val = int(x % md);
        }
        if (val < 0) {
            val += md;
        }
    }
    int operator()() { return val; }
    MInt& operator+= (MInt rhs) {
        if ((val += rhs.val) >= md) {
            val -= md;
        }
        return *this;
    }
    MInt& operator-= (MInt rhs) {
        if ((val -= rhs.val) < 0) {
            val += md;
        }
        return *this;
    }
    MInt& operator*= (MInt rhs) {
        val = int(1LL * val * rhs.val % md);
        return *this;
    }
    MInt inv() {
        return power(*this, md - 2);
    }
    MInt& operator/= (MInt rhs) {
        return *this *= rhs.inv();
    }
    bool operator== (MInt rhs) const {
        return val == rhs.val;
    }
    bool operator!= (MInt rhs) const {
        return val != rhs.val;
    }
};
MInt operator+ (MInt lhs, MInt rhs) {
    return lhs += rhs;
}
MInt operator- (MInt lhs, MInt rhs) {
    return lhs -= rhs;
}
MInt operator* (MInt lhs, MInt rhs) {
    return lhs *= rhs;
}
MInt operator/ (MInt lhs, MInt rhs) {
    return lhs /= rhs;
}
std::ostream& operator<< (std::ostream& os, MInt x) {
    return os << x.val;
}
std::string to_string(MInt x) {
    return to_string(x.val);
}

using Z = MInt;

struct node {
    int len;
    Z cnt;
    node() : len(-1), cnt(1) {}
    node(int x, Z y) : len(x), cnt(y) {}
};
node operator+ (node lhs, node rhs) {
    node res;
    if (lhs.len == rhs.len) {
        res.len = lhs.len;
        res.cnt = lhs.cnt + rhs.cnt;
    } else if (lhs.len > rhs.len) {
        res = lhs;
    } else {
        res = rhs;
    }
    return res;
}

#define def int mid = (l + r) >> 1, lv = v + 1, rv = v + ((mid - l + 1) << 1)
struct segtree {
    int n;
    std::vector<node> tree;
    segtree(int n_) : n(n_), tree(n << 1) {
        build();
    }
    void build() {
        auto dfs = [&](auto&& self, int v, int l, int r) -> void {
            if (l == r) {
                tree[v] = {-1, 1};
                return;
            }
            def;
            self(self, lv, l, mid);
            self(self, rv, mid + 1, r);
            tree[v] = tree[lv] + tree[rv];
        };
        dfs(dfs, 0, 0, n - 1);
    }
    void modify(int v, int l, int r, int p, int x, Z c) {
        if (l == r) {
            tree[v] = {x, c};
            return;
        }
        def;
        if (p <= mid) {
            modify(lv, l, mid, p, x, c);
        } else {
            modify(rv, mid + 1, r, p, x, c);
        }
        tree[v] = tree[lv] + tree[rv];
    }
    void modify(int p, int x, Z c) {
        modify(0, 0, n - 1, p, x, c);
    }
    node get(int v, int l, int r, int ql, int qr) {
        if (ql == l && r == qr) {
            return tree[v];
        }
        def;
        if (qr <= mid) {
            return get(lv, l, mid, ql, qr);
        } else if (mid + 1 <= ql) {
            return get(rv, mid + 1, r, ql, qr);
        } else {
            return get(lv, l, mid, ql, mid)
                 + get(rv, mid + 1, r, mid + 1, qr);
        }
    }
    node get(int l, int r) {
        return get(0, 0, n - 1, l, r);
    }
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int N;
    std::cin >> N;

    std::vector<int> A(N);
    for (int i = 0; i < N; ++i) {
        std::cin >> A[i];
    }

    std::vector<int> ord(N);
    std::iota(ord.begin(), ord.end(), 0);
    std::sort(ord.begin(), ord.end(), [&](auto lhs, auto rhs) {
        if (A[lhs] != A[rhs]) {
            return A[lhs] > A[rhs];
        }
        return lhs < rhs;
    });

    segtree seg(N);
    std::vector<node> pre(N), suf(N);
    for (auto i : ord) {
        node nd = seg.get(i, N - 1);
        if (nd.len == -1) {
            nd = {0, 1};
        }
        nd.len++;
        debug(i, nd.len, nd.cnt);
        suf[i] = nd;
        seg.modify(i, suf[i].len, suf[i].cnt);
    }

    std::sort(ord.begin(), ord.end(), [&](auto lhs, auto rhs) {
        if (A[lhs] != A[rhs]) {
            return A[lhs] < A[rhs];
        }
        return lhs > rhs;
    });

    seg.build();
    for (auto i : ord) {
        node nd = seg.get(i, N - 1);
        if (nd.len == -1) {
            nd = {0, 1};
        }
        nd.len++;
        debug(i, nd.len, nd.cnt);
        pre[i] = nd;
        seg.modify(i, pre[i].len, pre[i].cnt);
    }

    node res;
    for (int i = 0; i < N; ++i) {
        node x = {pre[i].len + suf[i].len - 1, pre[i].cnt * suf[i].cnt};
        res = res + x;
    }

    std::cout << res.len << ' ' << res.cnt * power(Z(2), N - res.len);

    return 0;
}

• Subtask 1: 105 / 140