Submission #369804

#	Time	Username	Problem	Language	Result	Execution time	Memory
369804		FatihSolak	Zoltan (COCI16_zoltan)	C++17	140 / 140	647 ms	23296 KiB

zoltan

#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 / 140