oj.uz

Submission #939438

# Submission time Handle Problem Language Result Execution time Memory
939438 2024-03-06T11:18:54 Z Warinchai Zoltan (COCI16_zoltan) C++14
42 / 140
 235 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;
int 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*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
42.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 15912 KB Output is correct
4 Correct 4 ms 15964 KB Output is correct
5 Correct 3 ms 15964 KB Output is correct
6 Correct 3 ms 16216 KB Output is correct
7 Incorrect 4 ms 15960 KB Output isn't correct
8 Incorrect 4 ms 15964 KB Output isn't correct
9 Incorrect 4 ms 15964 KB Output isn't correct
10 Incorrect 4 ms 15964 KB Output isn't correct
11 Incorrect 153 ms 17628 KB Output isn't correct
12 Incorrect 132 ms 17628 KB Output isn't correct
13 Incorrect 125 ms 17116 KB Output isn't correct
14 Incorrect 160 ms 17624 KB Output isn't correct
15 Incorrect 218 ms 17624 KB Output isn't correct
16 Incorrect 235 ms 17624 KB Output isn't correct
17 Incorrect 197 ms 17624 KB Output isn't correct
18 Incorrect 194 ms 17624 KB Output isn't correct
19 Incorrect 196 ms 17628 KB Output isn't correct
20 Incorrect 198 ms 17628 KB Output isn't correct