oj.uz

답안 #939442

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
939442 2024-03-06T11:20:53 Z Warinchai Zoltan (COCI16_zoltan) C++14
77 / 140
 277 ms 33416 KB 
#include<bits/stdc++.h>
using namespace std;
int ar[200005];
int md=1e9+7;
struct node{
    long long 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
77.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 31580 KB Output is correct
2 Correct 5 ms 31560 KB Output is correct
3 Correct 5 ms 31676 KB Output is correct
4 Correct 6 ms 31580 KB Output is correct
5 Correct 5 ms 31580 KB Output is correct
6 Correct 6 ms 31580 KB Output is correct
7 Correct 6 ms 31580 KB Output is correct
8 Correct 6 ms 31568 KB Output is correct
9 Correct 7 ms 31560 KB Output is correct
10 Correct 6 ms 31580 KB Output is correct
11 Runtime error 169 ms 33244 KB Memory limit exceeded
12 Runtime error 149 ms 33416 KB Memory limit exceeded
13 Correct 137 ms 32728 KB Output is correct
14 Runtime error 177 ms 33240 KB Memory limit exceeded
15 Runtime error 256 ms 33244 KB Memory limit exceeded
16 Runtime error 277 ms 33240 KB Memory limit exceeded
17 Runtime error 225 ms 33240 KB Memory limit exceeded
18 Runtime error 218 ms 33240 KB Memory limit exceeded
19 Runtime error 221 ms 33240 KB Memory limit exceeded
20 Runtime error 230 ms 33240 KB Memory limit exceeded