oj.uz

Submission #1082726

# Submission time Handle Problem Language Result Execution time Memory
1082726 2024-09-01T10:07:55 Z TrinhKhanhDung Zoltan (COCI16_zoltan) C++14
21 / 140
 34 ms 5312 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];

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;
}

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<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];
        }
    }

    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){
        add(ans, pw(2, N - ma));
    }
    cout << ma << ' ' << ans << '\n';
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
//    freopen("deggraph.inp", "r", stdin);
//    freopen("deggraph.out", "w", stdout);

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

    return 0;
}

Subtask #1
21.0 / 140.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2396 KB Output isn't correct
2 Incorrect 0 ms 2396 KB Output isn't correct
3 Incorrect 0 ms 2396 KB Output isn't correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Incorrect 1 ms 2396 KB Output isn't correct
8 Incorrect 1 ms 2396 KB Output isn't correct
9 Incorrect 1 ms 2396 KB Output isn't correct
10 Incorrect 1 ms 2396 KB Output isn't correct
11 Incorrect 22 ms 4356 KB Output isn't correct
12 Incorrect 21 ms 4164 KB Output isn't correct
13 Incorrect 23 ms 4184 KB Output isn't correct
14 Incorrect 23 ms 4568 KB Output isn't correct
15 Incorrect 31 ms 4840 KB Output isn't correct
16 Incorrect 34 ms 5312 KB Output isn't correct
17 Incorrect 30 ms 4656 KB Output isn't correct
18 Incorrect 29 ms 4680 KB Output isn't correct
19 Incorrect 29 ms 4680 KB Output isn't correct
20 Incorrect 29 ms 4680 KB Output isn't correct