oj.uz

답안 #939446

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
939446 2024-03-06T11:22:34 Z Warinchai Zoltan (COCI16_zoltan) C++14
77 / 140
 284 ms 33268 KB 
#include<bits/stdc++.h>
using namespace std;
int ar[200005];
int md=1e9+7;
struct node{
    int l;
    long long 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*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 6 ms 31580 KB Output is correct
2 Correct 5 ms 31564 KB Output is correct
3 Correct 5 ms 31580 KB Output is correct
4 Correct 5 ms 31580 KB Output is correct
5 Correct 5 ms 31580 KB Output is correct
6 Correct 5 ms 31580 KB Output is correct
7 Correct 7 ms 31560 KB Output is correct
8 Correct 6 ms 31580 KB Output is correct
9 Correct 6 ms 31580 KB Output is correct
10 Correct 6 ms 31576 KB Output is correct
11 Runtime error 176 ms 33240 KB Memory limit exceeded
12 Runtime error 145 ms 33244 KB Memory limit exceeded
13 Correct 138 ms 32732 KB Output is correct
14 Runtime error 189 ms 33240 KB Memory limit exceeded
15 Runtime error 236 ms 33244 KB Memory limit exceeded
16 Runtime error 284 ms 33244 KB Memory limit exceeded
17 Runtime error 220 ms 33268 KB Memory limit exceeded
18 Runtime error 222 ms 33244 KB Memory limit exceeded
19 Runtime error 230 ms 33244 KB Memory limit exceeded
20 Runtime error 219 ms 33240 KB Memory limit exceeded