oj.uz

Submission #1008754

# Submission time Handle Problem Language Result Execution time Memory
1008754 2024-06-26T17:36:21 Z doducanh Zoltan (COCI16_zoltan) C++14
140 / 140
 131 ms 19496 KB 
#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

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

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 71 ms 15296 KB Output is correct
12 Correct 63 ms 13280 KB Output is correct
13 Correct 59 ms 12484 KB Output is correct
14 Correct 93 ms 13764 KB Output is correct
15 Correct 108 ms 16828 KB Output is correct
16 Correct 131 ms 19496 KB Output is correct
17 Correct 103 ms 18960 KB Output is correct
18 Correct 99 ms 18884 KB Output is correct
19 Correct 107 ms 18880 KB Output is correct
20 Correct 79 ms 18880 KB Output is correct