Submission #581515

#	Time	Username	Problem	Language	Result	Execution time	Memory
581515		erto	Zoltan (COCI16_zoltan)	C++17	98 / 140	257 ms	20024 KiB

zoltan

#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;
 
    SegTree(int _n){
        n = _n+1;
        while(lsb(n) != n)
            n += lsb(n);
        tree.resize(2*n, {0, 0});
        n2 = n;
    }
 
    void update(int i, pair<int, int> val){
        i += n;
        tree[i] = comb(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: 98 / 140