Submission #542744

#	Time	Username	Problem	Language	Result	Execution time	Memory
542744		Sorting	Zoltan (COCI16_zoltan)	C++17	140 / 140	217 ms	13108 KiB

zoltan

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
template<class T> void check_min(T &a, const T &b){ a = (a < b) ? a : b; }
template<class T> void check_max(T &a, const T &b){ a = (a > b) ? a : b; }
#define all(x) (x).begin(), (x).end()

const int N = 2e5 + 3;
const int MOD = 1e9 + 7;

int n;
pair<int, int> a[N];

pair<int, int> dp[2][N];

struct SegmentTree{
    struct Node{
        int mx, cnt;

        Node(): mx(0), cnt(0){}
        Node(int mx, int cnt): mx(mx), cnt(cnt){}

        friend Node merge(const Node &l, const Node &r){
            Node res;
            res.mx = max(l.mx, r.mx);
            res.cnt = 0;
            res.cnt += (l.mx == res.mx) ? l.cnt : 0;
            res.cnt += (r.mx == res.mx) ? r.cnt : 0;
            if(res.cnt >= MOD) res.cnt -= MOD;
            return res;
        }
    } nd[4 * N];

    void init(int n){
        fill(nd, nd + 4 * n, Node());
    }

    void update(int idx, pair<int, int> val, int i = 0, int l = 1, int r = n){
        if(idx < l || r < idx) return;
        if(l == r){
            nd[i] = Node(val.first, val.second);
            return;
        }
        int mid = (l + r) >> 1;
        update(idx, val, 2 * i + 1, l, mid);
        update(idx, val, 2 * i + 2, mid + 1, r);
        nd[i] = merge(nd[2 * i + 1], nd[2 * i + 2]);
    }

    Node query(int sl, int sr, int i = 0, int l = 1, int r = n){
        if(sr < l || r < sl) return Node();
        if(sl <= l && r <= sr) return nd[i];
        int mid = (l + r) >> 1;
        return merge(query(sl, sr, 2 * i + 1, l, mid), query(sl, sr, 2 * i + 2, mid + 1, r));
    }
} seg_tr;

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

    cin >> n;
    for(int i = 1; i <= n; ++i){
        cin >> a[i].first;
        a[i].second = i;
    }
    sort(a + 1, a + n + 1);

    seg_tr.init(n);
    vector<int> to_update;
    for(int i = 1; i <= n; ++i){
        auto [mx, cnt] = seg_tr.query(a[i].second + 1, n);
        if(mx == 0) cnt = 1;
        dp[0][i] = pair{mx + 1, cnt};

        to_update.push_back(i);

        if(a[i].first != a[i + 1].first){
            for(int idx: to_update)
                seg_tr.update(a[idx].second, dp[0][idx]);
            to_update.clear();
        }
    }

    seg_tr.init(n);
    to_update.clear();
    for(int i = n; i >= 1; --i){
        auto [mx, cnt] = seg_tr.query(a[i].second + 1, n);
        if(mx == 0) cnt = 1;
        dp[1][i] = {mx + 1, cnt};

        to_update.push_back(i);

        if(a[i].first != a[i - 1].first){
            for(int idx: to_update)
                seg_tr.update(a[idx].second, dp[1][idx]);
            to_update.clear();
        }
    }

    dp[0][0].second = 1;
    dp[1][n + 1].second = 1;

    pair<int, ll> ans{0, 0};
    for(int i = 1; i <= n; ++i){
        pair<int, ll> cand{dp[0][i].first + dp[1][i].first - 1, (ll)dp[0][i].second * (ll)dp[1][i].second % MOD};
        if(cand.first == ans.first){
            ans.second += cand.second;
            if(ans.second >= MOD)
                ans.second -= MOD;
        }
        if(cand.first > ans.first)
            ans = cand;
    }
    int cnt = n - ans.first;
    while(cnt--){
        ans.second <<= 1;
        if(ans.second >= MOD) ans.second -= MOD;
    }

    cout << ans.first << " " << ans.second << "\n";
}

• Subtask 1: 140 / 140