Submission #1267805

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267805		uranium235	Zoltan (COCI16_zoltan)	C++17	140 / 140	140 ms	12872 KiB

zoltan

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const char nn = '\n';
const ll mod = 1000000007, inv = 500000004;

struct state {
    int max = 0;
    ll count = 0;
    void merge(state &l, state &r) {
        if (l.max > r.max) count = l.count;
        else if (r.max > l.max) count = r.count;
        else count = (l.count + r.count) % mod;
        max = std::max(l.max, r.max);
    }
};

class segtree {
    public:
        int n;
        vector<state> a;
        segtree(int n) : n(n), a(2 * n) {}
        void upd(int i, state &x) {
            for (a[i += n] = x; i > 1; i /= 2) a[i / 2].merge(a[i], a[i ^ 1]);
        }
        state qry(int l, int r) {
            state result;
            for (l += n, r += n; l < r; l /= 2, r /= 2) {
                if (l % 2 == 1) result.merge(result, a[l++]);
                if (r % 2 == 1) result.merge(a[--r], result);
            }
            return result;
        }
        void clear() {
            for (state &i : a) i.count = i.max = 0;
        }
};

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

    int n;
    cin >> n;
    vector<pair<int, int>> a(n);
    vector<int> comp(n), powtwo(n + 1);
    powtwo[0] = 1;
    for (int i = 0; i < n; i++) {
        cin >> comp[i];
        a[i] = {comp[i], i};
        powtwo[i + 1] = powtwo[i] * 2 % mod;
    }
    sort(comp.begin(), comp.end());
    comp.erase(unique(comp.begin(), comp.end()), comp.end());
    sort(a.begin(), a.end(), [](const pair<int, int> &l, const pair<int, int> &r) {
        if (l.first < r.first) return true;
        else if (l.first == r.first) return l.second < r.second;
        return false;
    });
    int ptr = 0;
    for (pair<int, int> &i : a) {
        if (comp[ptr] < i.first) ptr++;
        // cout << "comp " << i.first << " -> " << ptr << endl; 
        i.first = ptr;
    }
    assert(ptr == comp.size() - 1);
    ptr = 0;

    segtree tree(n);
    vector<state> cache(n);
    for (int i = 0; i < n; i++) {
        while (ptr < n && a[ptr].first == i) {
            pair<int, int> &p = a[ptr];
            state get = tree.qry(p.second + 1, n);
            if (get.max++ == 0) get.count = 1;
            tree.upd(p.second, get);
            cache[i].merge(cache[i], get);
            // cout << p.second << " " << get.max << " " << get.count << nn;
            ptr++;
        }
    }
    assert(ptr == n);
    sort(a.begin(), a.end(), [](const pair<int, int> &l, const pair<int, int> &r) {
        if (l.first > r.first) return true;
        else if (l.first == r.first) return l.second < r.second;
        return false;
    });
    tree.clear();
    state total, ans;
    total.count = 1;
    ptr = 0;
    for (int i = n; i >= 0; i--) {
        while (ptr < n && a[ptr].first == i) {
            pair<int, int> &p = a[ptr];
            state get = tree.qry(p.second + 1, n);
            if (get.max++ == 0) get.count = 1;
            tree.upd(p.second, get);
            total.merge(total, get);
            ptr++;
        }
        state curAns = total;
        if (i > 0) {
            curAns.max += cache[i - 1].max;
            curAns.count = curAns.count * cache[i - 1].count % mod;
            // cout << " " << cache[iter - 2].max << " " << cache[iter - 2].count;
        }
        curAns.count = curAns.count * powtwo[n - curAns.max];
        ans.merge(ans, curAns);

        // cout << i << " " << curAns.max << " " << curAns.count << nn;
    }
    assert(ptr == n);
        
    cout << ans.max << " " << (ans.count * inv % mod) << nn;
}

• Subtask 1: 140 / 140