oj.uz

Submission #939451

# Submission time Handle Problem Language Result Execution time Memory
939451 2024-03-06T11:25:08 Z Warinchai Zoltan (COCI16_zoltan) C++14
140 / 140
 277 ms 17724 KB 
#include<bits/stdc++.h>
using namespace std;
int ar[200005];
int md=1e9+7;
struct node{
    int l;
    int w;
    node(int a=0,int b=1){
        l=a,w=b;
    }
    friend node operator+(node a,node b){
        node c;
        c.l=max(a.l,b.l);
        c.w=a.l==b.l?a.w+b.w:a.l>b.l?a.w:b.w;
        if(c.l==0)c.w=1;
        c.w%=md;
        return c;
    }
};
struct segtree{
    node info[800005];
    void upd(int st,int en,int i,int pos,int len,int way){
        if(st>pos||en<pos)return;
        if(st==en)return void(info[i]=info[i]+node(len,way));
        int m=(st+en)/2;
        upd(st,m,i*2,pos,len,way);
        upd(m+1,en,i*2+1,pos,len,way);
        info[i]=info[i*2]+info[i*2+1];
    }
    node fans(int st,int en,int i,int l,int r){
        if(st>r||en<l)return node();
        if(st>=l&&en<=r)return info[i];
        int m=(st+en)/2;
        return fans(st,m,i*2,l,r)+fans(m+1,en,i*2+1,l,r);
    }
}lis,lds;
node inc[200005];
node de[200005];
node ans;
vector<int>v;
long long binpow(int a,int b){
    if(b==0)return 1;
    if(b==1)return a;
    if(b%2==0)return (binpow(a,b/2)*binpow(a,b/2))%md;
    return (binpow(a,b/2)*binpow(a,b/2)*a)%md;
}
int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;cin>>n;
    for(int i=1;i<=n;i++)cin>>ar[i],v.push_back(ar[i]);
    sort(v.begin(),v.end());
    int id=0;
    for(int i=n;i>=1;i--){
        id=lower_bound(v.begin(),v.end(),ar[i])-v.begin()+1;
        inc[i]=lds.fans(1,n,1,id+1,n);
        inc[i].l+=1;
        de[i]=lis.fans(1,n,1,1,id-1);
        de[i].l+=1;
        //cerr<<id<<":\n";
        //cerr<<inc[i].l<<" "<<inc[i].w<<"\n";
        //cerr<<de[i].l<<" "<<de[i].w<<"\n\n";
        lis.upd(1,n,1,id,de[i].l,de[i].w);
        lds.upd(1,n,1,id,inc[i].l,inc[i].w);
    }
    //cerr<<"\n";
    //cerr<<"\n";
    long long left,way,l;
    node temp;
    for(int i=1;i<=n;i++){
        left=n-(inc[i].l+de[i].l)+1;
        //cerr<<"left:"<<left<<"\n";
        way=binpow(2,left);
        way=(((way*inc[i].w)%md)*de[i].w)%md;
        l=inc[i].l+de[i].l-1;
        temp=node(l,way);
        //cerr<<l<<" "<<way<<"\n";
        ans=ans+temp;
    }
    cout<<ans.l<<" "<<ans.w%md;
}

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 15964 KB Output is correct
2 Correct 4 ms 15964 KB Output is correct
3 Correct 4 ms 15964 KB Output is correct
4 Correct 4 ms 15976 KB Output is correct
5 Correct 4 ms 15964 KB Output is correct
6 Correct 5 ms 15964 KB Output is correct
7 Correct 4 ms 15964 KB Output is correct
8 Correct 5 ms 16044 KB Output is correct
9 Correct 4 ms 15964 KB Output is correct
10 Correct 5 ms 16128 KB Output is correct
11 Correct 193 ms 17724 KB Output is correct
12 Correct 143 ms 17628 KB Output is correct
13 Correct 144 ms 17116 KB Output is correct
14 Correct 197 ms 17628 KB Output is correct
15 Correct 239 ms 17628 KB Output is correct
16 Correct 277 ms 17568 KB Output is correct
17 Correct 250 ms 17628 KB Output is correct
18 Correct 210 ms 17628 KB Output is correct
19 Correct 212 ms 17628 KB Output is correct
20 Correct 257 ms 17624 KB Output is correct