Submission #968685

#	Time	Username	Problem	Language	Result	Execution time	Memory
968685		RandomUser	Zoltan (COCI16_zoltan)	C++17	35 / 140	288 ms	47400 KiB

zoltan

#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define int long long
 
using namespace std;
 
using ll = long long;
using pii = pair<int, int>;
 
const int mod = 1000003;
const int maxn = 2e5 + 5;
 
ll exp(ll a, ll b) {
    ll ans = 1;
    while(b) {
        if(b & 1) ans = (ans * a) % mod;
        a = (a * a) % mod;
        b /= 2;
    }
    return ans;
}
 
struct SegTree {
    int n;
    vector<pii> tree;
 
    SegTree(int _n) {
        n = _n;
        tree.resize(4*n+5);
    }
 
    pii merge(pii a, pii b) {
        if(a.first > b.first) return a;
        if(a.first < b.first) return b;
        return { a.first, (a.second + b.second) % mod };
    }
 
    void update(int u, int tl, int tr, int p, int v, int w) {
        if(tl == tr) {
            tree[u] = merge(tree[u], { v, w });
        } else {
            int tm = (tl + tr) / 2;
            if(p <= tm)
                update(2*u, tl, tm, p, v, w);
            else
                update(2*u+1, tm+1, tr, p, v, w);
            tree[u] = merge(tree[2*u], tree[2*u+1]);
        }
    }
 
    pii query(int u, int tl, int tr, int l, int r) {
        if(tl > tr || l > tr || tl > r) return { 0, 0 };
        if(l <= tl && tr <= r) return tree[u];
        int tm = (tl + tr) / 2;
        return merge(
            query(2*u, tl, tm, l, r),
            query(2*u+1, tm+1, tr, l, r)
        );
    }
 
    void update(int p, ll v, ll w) { update(1, 0, n-1, p, v, w); }
    pii query(int l, int r) { return query(1, 0, n-1, l, r); }
};
 
int32_t main() {
    int n;
    cin >> n;
 
    vector<pii> lis(n), lds(n), v(n);
    for(int i=0; i<n; i++) cin >> v[i].first, v[i].second = i;
    sort(all(v), [&](pii &a, pii &b) {
        if(a.first == b.first) return a.second < b.second;
        return a.first > b.first;
    });
 
    set<int> s; s.insert(0);
    for(auto &x : v) s.insert(x.first);
    vector<int> comp(all(s));
 
    SegTree dpL(n+1), dpR(n+1);
    dpL.update(n, 0, 1); dpR.update(n, 0, 1);
 
    for(auto [val, i] : v) {
        auto [a, b] = dpL.query(i+1, n);
        lis[i] = { a + 1, b };
        dpL.update(i, a + 1, b);
    }
 
    sort(all(v), [&](pii &a, pii &b) {
        if(a.first == b.first) return a.second < b.second;
        return a.first < b.first;
    });
    for(auto [val, i] : v) {
        auto [a, b] = dpR.query(i+1, n);
        lds[i] = { a + 1, b };
        dpR.update(i, a + 1, b);
    }
 
    ll len=0, ways=0;
    for(int i=0; i<n; i++) {
        ll L = lis[i].first + lds[i].first - 1;
        ll W = (lis[i].second * lds[i].second) % mod;
        if(L > len) len = L, ways = W;
        else if(L == len) ways = (ways + W) % mod;
    }
 
    cout << len << '\n' << ways * exp(2, n - len) % mod << '\n';
    return 0;
}

• Subtask 1: 35 / 140