Submission #1008754

#	Time	Username	Problem	Language	Result	Execution time	Memory
1008754		doducanh	Zoltan (COCI16_zoltan)	C++14	140 / 140	131 ms	19496 KiB

zoltan

#include <bits/stdc++.h>

using namespace std;
#define int long long
#define fi first
#define se second
const int maxn=2e5+7;
const int mod=1e9+7;
const int maxx=2e9;
pair<int,int> cmax(pair<int,int>a,pair<int,int>b)
{
    if(a.fi<b.fi)a=b;
    else{
        if(a.fi==b.fi&&a.fi!=0)a.se=(a.se+b.se)%mod;
    }
    return a;
}
vector<int>v;
int id(int x)
{
    return lower_bound(v.begin(),v.end(),x)-v.begin()+1;
}
struct BIT
{
    int n;
    vector<pair<int,int>>t;
    BIT(){}
    BIT(int n):n(n),t(n+7,{0,1}){}
    void upi(int x,pair<int,int> val){
        for(;x<=n;x+=(x&(-x)))t[x]=cmax(t[x],val);
    }
    void upd(int x,pair<int,int>val){
        for(;x;x-=(x&(-x)))t[x]=cmax(t[x],val);
    }
    pair<int,int>geti(int x)
    {
        if(x<=0)return {0,1};
        pair<int,int>res={0,1};
        for(;x;x-=(x&(-x)))res=cmax(res,t[x]);
        return res;
    }
    pair<int,int>getd(int x)
    {
        if(x<=0)return {0,1};
        pair<int,int>res={0,1};
        for(;x<=n;x+=(x&(-x)))res=cmax(res,t[x]);
        return res;
    }
};
int n;
pair<int,int> A[maxn];
pair<int,int> B[maxn];
int a[maxn];
int p[maxn];
main()
{
    cin>>n;
    p[0]=1;
    for(int i=1;i<=n;i++){
        p[i]=(p[i-1]*2)%mod;
    }
    BIT up(n);
    BIT down(n);
    for(int i=1;i<=n;i++){
        cin>>a[i];
        v.push_back(a[i]);
    }
    sort(v.begin(),v.end());
    for(int i=1;i<=n;i++){
        a[i]=id(a[i]);
    }
    for(int i=n;i>=1;i--){
        pair<int,int>p=up.geti(a[i]-1);
        A[i]=p;
        up.upi(a[i],make_pair(p.fi+1,p.se));
    }
    for(int i=n;i>=1;i--){
        pair<int,int>p=down.getd(a[i]+1);
        B[i]=p;
        down.upd(a[i],make_pair(p.fi+1,p.se));
    }
//    for(int i=1;i<=n;i++){
//        cout<<A[i].fi<<" "<<A[i].se<<" "<<B[i].fi<<" "<<B[i].se<<"\n";
//    }
    pair<int,int>res={0,0};
    for(int i=1;i<=n;i++){
        res=cmax(res,{A[i].fi+B[i].fi+1,((A[i].se*B[i].se)%mod*p[n-(A[i].fi+B[i].fi+1)])%mod});
    }
    cout<<res.fi<<" "<<res.se;
}

Compilation message (stderr)

zoltan.cpp:55:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   55 | main()
      | ^~~~

• Subtask 1: 140 / 140