oj.uz

Submission #581508

# Submission time Handle Problem Language Result Execution time Memory
581508 2022-06-22T17:16:25 Z erto Zoltan (COCI16_zoltan) C++17
0 / 140
 297 ms 38328 KB 
#include <bits/stdc++.h>
typedef long long int ll;
#define INF ll(1e9 + 7)
#define INF2 998244353
#define N (ll)(2e5 + 5)
using namespace std;
#define int ll
#define lsb(x) (x & (-x))

int n, g, h,m,  q,z,t1,t2, ans, ans2, n2; 
vector<int> v;
int a[N];
pair<int, int> p1, p2;

pair<int, int> comb(pair<int, int> x, pair<int, int> y){
    if(x.first > y.first){
        return x;
    }
    else if(x.first < y.first){
        return y;
    }
    else{
        return {x.first, x.second + y.second};
    }
}

struct SegTree{
    int n;
    vector<pair<int, int>> tree, tree2;
 
    SegTree(int _n){
        n = _n+1;
        while(lsb(n) != n)
            n += lsb(n);
        tree.resize(2*n, {0, 0});
        tree2.resize(2*n, {0, 0});
        n2 = n;
    }
 
    void update(int i, pair<int, int> val){
        i += n;
        tree[i] = val;

        while(i >>= 1){
            tree[i] = comb(tree[i * 2] , tree[i * 2 + 1]);
        }
    }
 
    pair<int, int> query(int ql, int qr){ return query(1, 0, n-1, ql, qr); }
    pair<int, int> query(int i, int lb, int rb, int ql, int qr){
        if(ql <= lb && rb <= qr){
            return tree[i];
        }
        if(qr < lb || rb < ql)
            return {0, 0};
        int md = (lb+rb)/2;
        return comb(query(2*i, lb, md, ql, qr) , query(2*i+1, md+1, rb, ql, qr));
    }
};

void solve(){
    cin >> n;
    SegTree s(N), s2(N);

    
    for(int i=1; i<=n; i++){
        cin >> a[i];
        v.push_back(a[i]);
    }
    sort(v.begin(), v.end());

    for(int i=1; i<=n; i++){
        a[i] = (lower_bound(v.begin(), v.end(), a[i]) - v.begin()) + 1;
    }

    for(int i=n; i>=1; i--){
        p1 = s.query(a[i] + 1, n2 - 1);
        p2 = s2.query(0, a[i] - 1);
        p1.first++;
        p2.first++;
        if(!p1.second)p1.second = 1;
        if(!p2.second)p2.second = 1;

       

        if(ans < p1.first + p2.first - 1){
            ans = p1.first + p2.first - 1;
            ans2 = (p1.second * p2.second) % INF;
        }
        else if(ans == p1.first + p2.first - 1){
            ans2 += (p1.second * p2.second) % INF;
        }
        s.update(a[i], {p1.first , p1.second});
        s2.update(a[i], {p2.first, p2.second});
    }

    for(int i=0; i< n - ans; i++){
        ans2 = (ans2 * 2) % INF;
    }
    cout << ans << " " <<  ans2;
}

signed main(){
    //freopen("trapezoid.in", "r", stdin);
    //freopen("trapezoid.out", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int T = 1;
    //cin>>T;
    while (T--){
        solve();
    }
}

Subtask #1
0 / 140.0

# Verdict Execution time Memory Grader output
1 Runtime error 15 ms 33108 KB Memory limit exceeded
2 Runtime error 14 ms 33108 KB Memory limit exceeded
3 Runtime error 14 ms 33176 KB Memory limit exceeded
4 Runtime error 14 ms 33108 KB Memory limit exceeded
5 Runtime error 13 ms 33108 KB Memory limit exceeded
6 Runtime error 13 ms 33108 KB Memory limit exceeded
7 Runtime error 14 ms 33196 KB Memory limit exceeded
8 Runtime error 13 ms 33120 KB Memory limit exceeded
9 Runtime error 14 ms 33108 KB Memory limit exceeded
10 Runtime error 14 ms 33108 KB Memory limit exceeded
11 Runtime error 131 ms 37448 KB Memory limit exceeded
12 Runtime error 127 ms 37364 KB Memory limit exceeded
13 Runtime error 103 ms 36292 KB Memory limit exceeded
14 Runtime error 167 ms 37704 KB Memory limit exceeded
15 Runtime error 214 ms 37844 KB Memory limit exceeded
16 Runtime error 297 ms 38328 KB Memory limit exceeded
17 Runtime error 174 ms 37724 KB Memory limit exceeded
18 Runtime error 173 ms 37700 KB Memory limit exceeded
19 Runtime error 179 ms 37796 KB Memory limit exceeded
20 Runtime error 191 ms 37656 KB Memory limit exceeded