oj.uz

Submission #369801

# Submission time Handle Problem Language Result Execution time Memory
369801 2021-02-22T12:44:52 Z FatihSolak Zoltan (COCI16_zoltan) C++17
70 / 140
 686 ms 37356 KB 
#include <bits/stdc++.h>
#define N 200005
#define MOD 1000000007
using namespace std;
struct Node{
    long long 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]);
}
long long binpow(long long a,long long b){
    long long ret = 1;
    while(b){
        if(b&1){
            ret = ret*a%MOD;
        }
        a = 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++;
    }
    long long 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;
        }
        long long ln = l.val1 + r.val2+1;
        long long occ = 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
70.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 25452 KB Output is correct
2 Correct 15 ms 25452 KB Output is correct
3 Correct 15 ms 25472 KB Output is correct
4 Correct 13 ms 25452 KB Output is correct
5 Correct 13 ms 25452 KB Output is correct
6 Correct 13 ms 25452 KB Output is correct
7 Correct 19 ms 25472 KB Output is correct
8 Correct 15 ms 25452 KB Output is correct
9 Correct 14 ms 25452 KB Output is correct
10 Correct 14 ms 25452 KB Output is correct
11 Runtime error 364 ms 34796 KB Memory limit exceeded
12 Runtime error 328 ms 33516 KB Memory limit exceeded
13 Runtime error 290 ms 33004 KB Memory limit exceeded
14 Runtime error 439 ms 33772 KB Memory limit exceeded
15 Runtime error 568 ms 35692 KB Memory limit exceeded
16 Runtime error 686 ms 37356 KB Memory limit exceeded
17 Runtime error 445 ms 35436 KB Memory limit exceeded
18 Runtime error 424 ms 35340 KB Memory limit exceeded
19 Runtime error 412 ms 35308 KB Memory limit exceeded
20 Runtime error 424 ms 35344 KB Memory limit exceeded