oj.uz

Submission #939440

# Submission time Handle Problem Language Result Execution time Memory
939440 2024-03-06T11:19:52 Z Warinchai Zoltan (COCI16_zoltan) C++14
119 / 140
 247 ms 17628 KB 
#include<bits/stdc++.h>
using namespace std;
int ar[200005];
int md=1e9+7;
struct node{
    int l,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(long long a,long long 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*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;
}

Subtask #1
119.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 5 ms 15964 KB Output is correct
5 Correct 3 ms 15964 KB Output is correct
6 Correct 4 ms 15964 KB Output is correct
7 Correct 4 ms 16052 KB Output is correct
8 Correct 5 ms 16216 KB Output is correct
9 Correct 4 ms 15960 KB Output is correct
10 Correct 4 ms 15964 KB Output is correct
11 Correct 166 ms 17628 KB Output is correct
12 Correct 141 ms 17628 KB Output is correct
13 Correct 131 ms 17116 KB Output is correct
14 Incorrect 185 ms 17624 KB Output isn't correct
15 Incorrect 213 ms 17624 KB Output isn't correct
16 Incorrect 247 ms 17624 KB Output isn't correct
17 Correct 204 ms 17628 KB Output is correct
18 Correct 202 ms 17628 KB Output is correct
19 Correct 203 ms 17628 KB Output is correct
20 Correct 205 ms 17628 KB Output is correct