oj.uz

Submission #369804

# Submission time Handle Problem Language Result Execution time Memory
369804 2021-02-22T12:48:15 Z FatihSolak Zoltan (COCI16_zoltan) C++17
140 / 140
 647 ms 23296 KB 
#include <bits/stdc++.h>
#define N 200005
#define MOD 1000000007
using namespace std;
struct Node{
    int val1,val2,occur1,occur2;
    Node(){
        val1 = 0,val2 = 0,occur1 = 0,occur2 = 0;
    }
};
Node t[4*N];
Node cmp(Node a,Node b){
    Node ret;
    if(a.val1 == b.val1){
        ret.val1 = a.val1;
        ret.occur1 = (a.occur1 + b.occur1)%MOD;
    }
    else{
        if(a.val1 > b.val1){
            ret.val1 = a.val1;
            ret.occur1 = a.occur1;
        }
        else{
            ret.val1 = b.val1;
            ret.occur1 = b.occur1;
        }
    }
    if(a.val2 == b.val2){
        ret.val2 = a.val2;
        ret.occur2 = (a.occur2 + b.occur2)%MOD;
    }
    else{
        if(a.val2 > b.val2){
            ret.val2 = a.val2;
            ret.occur2 = a.occur2;
        }
        else{
            ret.val2 = b.val2;
            ret.occur2 = b.occur2;
        }
    }
    return ret;
}
int arr[N];
map<int,int> mp;
Node get(int v,int tl,int tr,int l,int r){
    if(tr < l || r < tl){
        return Node();
    }
    if(l <= tl && tr <= r){
        return t[v];
    }
    int tm = (tl+tr)/2;
    Node lc = get(v*2,tl,tm,l,r);
    Node rc = get(v*2+1,tm+1,tr,l,r);
    return cmp(lc,rc);
}
void upd(int v,int l,int r,int pos,Node val){
    if(l == r){
        t[v] = cmp(t[v],val);
        return;
    }
    int m = (l+r)/2;
    if(pos <= m)
        upd(v*2,l,m,pos,val);
    else upd(v*2+1,m+1,r,pos,val);
    t[v] = cmp(t[v*2],t[v*2+1]);
}
int binpow(int a,int b){
    int ret = 1;
    while(b){
        if(b&1){
            ret = 1ll*ret*a%MOD;
        }
        a = 1ll*a *a%MOD;
        b/=2;
    }
    return ret;
}
void solve(){
    int n;
    cin >> n;
    for(int i=0;i<n;i++){
        cin >> arr[i];
        mp[arr[i]]++;
    }
    int cnt = 1;
    for(auto &u:mp){
        u.second = cnt++;
    }
    int ans1 = 0,ans2=0;
    for(int i=n-1;i>=0;i--){
        Node l = get(1,1,n,1,mp[arr[i]]-1);
        Node r = get(1,1,n,mp[arr[i]]+1,n);
        if(l.val1 == 0){
            l.occur1 = 1;
        }
        if(r.val2 == 0){
            r.occur2 = 1;
        }
        int ln = l.val1 + r.val2+1;
        int occ = 1ll*l.occur1 * r.occur2%MOD * binpow(2,n-ln)%MOD;
        if(ln == ans1){
            ans2 = (ans2+occ)%MOD;
        }
        if(ln > ans1){
            ans1 = ln;
            ans2 = occ;
        }
        Node up;
        up.val1 = l.val1 + 1;
        up.occur1 = l.occur1;
        up.val2 = r.val2 + 1;
        up.occur2 = r.occur2;
        upd(1,1,n,mp[arr[i]],up);
        //cout << ans1 << " " << ans2 << endl;
    }
    cout << ans1 << " " << ans2;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    #ifdef Local
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    #ifdef Local
    cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
}

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12908 KB Output is correct
2 Correct 10 ms 12908 KB Output is correct
3 Correct 10 ms 12908 KB Output is correct
4 Correct 86 ms 12920 KB Output is correct
5 Correct 9 ms 12908 KB Output is correct
6 Correct 9 ms 12904 KB Output is correct
7 Correct 10 ms 12908 KB Output is correct
8 Correct 10 ms 12908 KB Output is correct
9 Correct 11 ms 13036 KB Output is correct
10 Correct 11 ms 12908 KB Output is correct
11 Correct 342 ms 21100 KB Output is correct
12 Correct 294 ms 20076 KB Output is correct
13 Correct 309 ms 19820 KB Output is correct
14 Correct 405 ms 20076 KB Output is correct
15 Correct 570 ms 21900 KB Output is correct
16 Correct 647 ms 23296 KB Output is correct
17 Correct 376 ms 21772 KB Output is correct
18 Correct 366 ms 21820 KB Output is correct
19 Correct 383 ms 21712 KB Output is correct
20 Correct 380 ms 21816 KB Output is correct