oj.uz

Submission #1082736

# Submission time Handle Problem Language Result Execution time Memory
1082736 2024-09-01T10:51:24 Z TrinhKhanhDung Zoltan (COCI16_zoltan) C++14
140 / 140
 128 ms 26832 KB 
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define sz(x) (int)x.size()
#define ALL(v) v.begin(),v.end()
#define MASK(k) (1LL << (k))
#define BIT(x, i) (((x) >> (i)) & 1)
#define oo (ll)1e18
#define INF (ll)1e9
#define MOD (ll)(1e9 + 7)

using namespace std;

template<class T1, class T2>
    bool maximize(T1 &a, T2 b){if(a < b){a = b; return true;} return false;}

template<class T1, class T2>
    bool minimize(T1 &a, T2 b){if(a > b){a = b; return true;} return false;}

template<class T1, class T2>
    void add(T1 &a, T2 b){a += b; if(a >= MOD) a -= MOD;}

template<class T1, class T2>
    void sub(T1 &a, T2 b){a -= b; if(a < 0) a += MOD;}

template<class T>
    void cps(T &v){sort(ALL(v)); v.resize(unique(ALL(v)) - v.begin());}

const int MAX = 2e5 + 10;

int N;
int a[MAX], f[MAX], g[MAX], ff[MAX], gg[MAX];

int pw(int a, int n){
    if(n < 0) return 0;
    int ans = 1;
    while(n){
        if(n & 1) ans = 1LL * ans * a % MOD;
        n >>= 1;
        a = 1LL * a * a % MOD;
    }
    return ans;
}

struct fen{
    vector<int> tree;
    int n;

    fen(int _n = 0){
        n = _n;
        tree.resize(n + 3, 0);
    }

    void upd(int p, int c){
        while(p <= n){
            add(tree[p], c);
            p += p & -p;
        }
    }

    int get(int p){
        int ans = 0;
        while(p > 0){
            add(ans, tree[p]);
            p -= p & -p;
        }
        return ans;
    }
};

void solve(){
    cin >> N;
    for(int i=1; i<=N; i++){
        cin >> a[i];
    }

    {
        vector<int> len(N + 3, INF + 10);
        len[0] = 0;
        for(int i=N; i>=1; i--){
            int x = lower_bound(ALL(len), a[i]) - len.begin();
            f[i] = x;
            len[x] = a[i];
        }
        vector<fen> bit(N + 3);
        vector<vector<int>> ord(N + 3);
        ord[0].push_back(0);
        for(int i=N; i>=1; i--){
            ord[f[i]].push_back(a[i]);
        }
        for(int i=0; i<=N; i++){
            cps(ord[i]);
            bit[i] = fen(sz(ord[i]));
        }
        bit[0].upd(1, 1);
        for(int i=N; i>=1; i--){
            int p = lower_bound(ALL(ord[f[i] - 1]), a[i]) - ord[f[i] - 1].begin();
            ff[i] = bit[f[i] - 1].get(p);
            p = lower_bound(ALL(ord[f[i]]), a[i]) - ord[f[i]].begin() + 1;
            bit[f[i]].upd(p, ff[i]);
        }
    }

    {
        vector<int> len(N + 3, -INF - 10);
        len[0] = INF;
        for(int i=N; i>=1; i--){
            int l = 0, r = N;
            while(l < r){
                int m = (l + r) >> 1;
                if(len[m] <= a[i]){
                    r = m;
                }
                else{
                    l = m + 1;
                }
            }
            g[i] = r;
            len[r] = a[i];
        }
        vector<fen> bit(N + 3);
        vector<vector<int>> ord(N + 3);
        ord[0].push_back(INF + 10);
        for(int i=N; i>=1; i--){
            ord[g[i]].push_back(a[i]);
        }
        for(int i=0; i<=N; i++){
            cps(ord[i]);
            bit[i] = fen(sz(ord[i]));
        }
        bit[0].upd(1, 1);
        for(int i=N; i>=1; i--){
            int p = upper_bound(ALL(ord[g[i] - 1]), a[i]) - ord[g[i] - 1].begin();
            gg[i] = (bit[g[i] - 1].get(sz(ord[g[i] - 1])) - bit[g[i] - 1].get(p) + MOD * MOD) % MOD;
            p = lower_bound(ALL(ord[g[i]]), a[i]) - ord[g[i]].begin() + 1;
            bit[g[i]].upd(p, gg[i]);
//            cout << i << ' ' << g[i] << ' ' << gg[i] << '\n';
        }
    }

    int ma = 0;
    for(int i=1; i<=N; i++){
        maximize(ma, g[i] + f[i] - 1);
    }
    int ans = 0;
    for(int i=1; i<=N; i++) if(ma == g[i] + f[i] - 1){
//        cout << i << ' ' << ff[i] << ' ' << gg[i] << '\n';
        add(ans, 1LL * ff[i] * gg[i] % MOD * pw(2, N - ma) % MOD);
    }
    cout << ma << ' ' << ans << '\n';
}

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

    int t = 1;
//    cin >> t;
    while(t--){
        solve();
    }

    return 0;
}

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 476 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 82 ms 21976 KB Output is correct
12 Correct 65 ms 19252 KB Output is correct
13 Correct 64 ms 18200 KB Output is correct
14 Correct 82 ms 18192 KB Output is correct
15 Correct 100 ms 22516 KB Output is correct
16 Correct 128 ms 26012 KB Output is correct
17 Correct 86 ms 26724 KB Output is correct
18 Correct 91 ms 26632 KB Output is correct
19 Correct 96 ms 26832 KB Output is correct
20 Correct 91 ms 26724 KB Output is correct