oj.uz

Submission #581515

# Submission time Handle Problem Language Result Execution time Memory
581515 2022-06-22T17:21:07 Z erto Zoltan (COCI16_zoltan) C++17
98 / 140
 257 ms 20024 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;
 
    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.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16724 KB Output is correct
2 Correct 8 ms 16636 KB Output is correct
3 Correct 8 ms 16724 KB Output is correct
4 Correct 8 ms 16652 KB Output is correct
5 Correct 7 ms 16728 KB Output is correct
6 Correct 8 ms 16744 KB Output is correct
7 Correct 8 ms 16724 KB Output is correct
8 Correct 8 ms 16724 KB Output is correct
9 Correct 8 ms 16724 KB Output is correct
10 Correct 9 ms 16724 KB Output is correct
11 Incorrect 161 ms 19920 KB Output isn't correct
12 Incorrect 120 ms 19868 KB Output isn't correct
13 Incorrect 126 ms 18896 KB Output isn't correct
14 Incorrect 160 ms 19868 KB Output isn't correct
15 Incorrect 228 ms 19960 KB Output isn't correct
16 Incorrect 257 ms 19936 KB Output isn't correct
17 Correct 177 ms 19972 KB Output is correct
18 Correct 194 ms 20024 KB Output is correct
19 Correct 191 ms 20016 KB Output is correct
20 Correct 190 ms 20004 KB Output is correct