oj.uz

답안 #939436

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
939436 2024-03-06T11:17:07 Z Warinchai Zoltan (COCI16_zoltan) C++14
70 / 140
 316 ms 35192 KB 
#include<bits/stdc++.h>
#define int long long
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";
    int 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
70.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 31576 KB Output is correct
2 Correct 5 ms 31580 KB Output is correct
3 Correct 5 ms 31676 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 31580 KB Output is correct
8 Correct 15 ms 31832 KB Output is correct
9 Correct 7 ms 31580 KB Output is correct
10 Correct 6 ms 31580 KB Output is correct
11 Runtime error 180 ms 34924 KB Memory limit exceeded
12 Runtime error 170 ms 35192 KB Memory limit exceeded
13 Runtime error 146 ms 33828 KB Memory limit exceeded
14 Runtime error 204 ms 34776 KB Memory limit exceeded
15 Runtime error 268 ms 34776 KB Memory limit exceeded
16 Runtime error 316 ms 34776 KB Memory limit exceeded
17 Runtime error 256 ms 35024 KB Memory limit exceeded
18 Runtime error 233 ms 35016 KB Memory limit exceeded
19 Runtime error 220 ms 35028 KB Memory limit exceeded
20 Runtime error 255 ms 35028 KB Memory limit exceeded