oj.uz

Submission #787074

# Submission time Handle Problem Language Result Execution time Memory
787074 2023-07-18T18:41:52 Z Ahmed57 Zoltan (COCI16_zoltan) C++17
105 / 140
 401 ms 34828 KB 
#include<bits/stdc++.h>
#include<queue>
using namespace std;
long long n;long long arr[200005];
long long mod = 1000000007;
struct node{
    long long 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<long long,long long> 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
105.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 270 ms 30648 KB Output is correct
12 Correct 198 ms 27644 KB Output is correct
13 Correct 185 ms 22512 KB Output is correct
14 Correct 251 ms 26832 KB Output is correct
15 Correct 335 ms 31288 KB Output is correct
16 Runtime error 401 ms 34828 KB Memory limit exceeded
17 Runtime error 256 ms 33252 KB Memory limit exceeded
18 Runtime error 264 ms 33240 KB Memory limit exceeded
19 Runtime error 251 ms 33220 KB Memory limit exceeded
20 Runtime error 248 ms 33184 KB Memory limit exceeded