oj.uz

Submission #787075

# Submission time Handle Problem Language Result Execution time Memory
787075 2023-07-18T18:43:23 Z Ahmed57 Zoltan (COCI16_zoltan) C++17
140 / 140
 388 ms 26840 KB 
#include<bits/stdc++.h>
#include<queue>
using namespace std;
int n;int arr[200005];
int mod = 1000000007;
struct node{
    int ma,cnt;
}seg[800001],em;
node combine(node a,node b){
    node ans;
    ans.ma = max(a.ma,b.ma);
    if(a.ma==b.ma)ans.cnt = (a.cnt+b.cnt)%mod;
    if(a.ma>b.ma)ans.cnt = a.cnt;
    if(b.ma>a.ma)ans.cnt = b.cnt;
    return ans;
}
void build(int p,int l,int r){
    if(l==r){
        seg[p] = em;
        return ;
    }
    int md = (l+r)/2;
    build(p*2,l,md);build(p*2+1,md+1,r);
    seg[p] = combine(seg[p*2],seg[p*2+1]);
}
void update(int p,int l,int r,int idx,pair<int,int> val){
    if(l==r){
        if(val.first>seg[p].ma){
            seg[p].ma = val.first;
            seg[p].cnt = val.second;
        }else if(val.first==seg[p].ma){
            seg[p].cnt += val.second;
        }
        return ;
    }int md = (l+r)/2;
    if(idx<=md)update(p*2,l,md,idx,val);
    else update(p*2+1,md+1,r,idx,val);
    seg[p] = combine(seg[p*2],seg[p*2+1]);
}
node query(int p,int l,int r,int lq,int rq){
    if(l>rq||r<lq||l>r)return em;
    if(l>=lq&&r<=rq)return seg[p];
    int md = (l+r)/2;
    return combine(query(p*2,l,md,lq,rq),query(p*2+1,md+1,r,lq,rq));
}
int main(){
    em.ma = -1 , em.cnt = 1;
    cin>>n;
    for(int i = 0;i<n;i++){
        cin>>arr[i];arr[i]++;
    }
    arr[n] = 1;
    map<int,int> comp,sav;
    for(int i = 0;i<=n;i++)comp[arr[i]]++;
    int z = 0;
    for(auto i:comp){
        sav[i.first] = ++z;
    }
    for(int i = 0;i<=n;i++)arr[i] = sav[arr[i]];
    build(1,1,z);
    node dpr[n+1];
    for(int i = n;i>=0;i--){
        if(i==n){
            dpr[i].ma = 0 , dpr[i].cnt = 1;
        }else{
            dpr[i] = query(1,1,z,1,arr[i]-1);
            dpr[i].ma ++;
            //dpr[i] = combine(dpr[i+1],dpr[i]);
            //cout<<dpr[i].cnt<<" "<<dpr[i].ma<<endl;
        }
        update(1,1,z,arr[i],make_pair(dpr[i].ma,dpr[i].cnt));
    }
    node dpl[n+1];
    build(1,1,z);
    for(int i =1;i<n;i++){
        update(1,1,z,arr[i-1],make_pair(dpr[i-1].ma,dpr[i-1].cnt));
        dpl[i] = query(1,1,z,1,arr[i]-1);
        dpl[i].ma ++;
        //cout<<dpl[i].ma<<endl;
        //if(i>1)dpl[i] = combine(dpl[i-1],dpl[i]);
        //else dpl[i] = combine(dpr[0],dpl[i]);
        update(1,1,z,arr[i],make_pair(dpl[i].ma,dpl[i].cnt));
    }
    long long xd = 1;
    long long mi = -1 , su = 0;
    for(int i = 0;i<n;i++){
        if(mi<dpr[i].ma){
            mi = dpr[i].ma;
            su = 0;
        }if(mi==dpr[i].ma){
            su+=dpr[i].cnt;
        }
    }
    for(int i = 1;i<n;i++){
        if(mi<dpl[i].ma){
            mi = dpl[i].ma;
            su = 0;
        }if(mi==dpl[i].ma){
            su+=dpl[i].cnt;
        }
    }
    for(int i = 0;i<n-mi;i++){
        xd*=2;xd%=mod;
    }
    cout<<mi<<" "<<(su*xd)%mod<<endl;
}

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 234 ms 22216 KB Output is correct
12 Correct 196 ms 19904 KB Output is correct
13 Correct 189 ms 17024 KB Output is correct
14 Correct 242 ms 19976 KB Output is correct
15 Correct 311 ms 23812 KB Output is correct
16 Correct 388 ms 26840 KB Output is correct
17 Correct 252 ms 24024 KB Output is correct
18 Correct 261 ms 23952 KB Output is correct
19 Correct 256 ms 23912 KB Output is correct
20 Correct 249 ms 24012 KB Output is correct