Submission #548028

#	Time	Username	Problem	Language	Result	Execution time	Memory
548028		FEDIKUS	Zoltan (COCI16_zoltan)	C++17	112 / 140	318 ms	13388 KiB

zoltan

#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define xx first
#define yy second
#define ff(i,s,f) for(int (i)=s;(i)<(f);(i)++)
#define fb(i,s,f) for(int (i)=s-1;(i)>=f;(i)--)
#define ffi(i,s,f) for(int (i)=s;(i)<=(f);(i)++)
#define fbi(i,s,f) for(int (i)=s;(i)>=(f);(i)--)
#define srt(a) sort(a.begin(),a.end());
#define srtg(a,int) sort(a.begin(),a.end(),greater<int>())
#define lb(a,x) lower_bound(a.begin(),a.end(),x)
#define ub(a,x) upper_bound(a.begin(),a.end(),x)
#define fnd(a,x) find(a.begin(),a.end(),x)
#define vstart auto startt=chrono::system_clock::now()
#define vend auto endd=chrono::system_clock::now()
#define vvreme chrono::duration<double> vremee=endd-startt
#define ios ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef string str;

const int maxn=2e5+10;
const int mod=1e9+7;

int niz[maxn];
int compr[maxn];
pii seginc[4*maxn];
pii segdec[4*maxn];
pii incr[maxn];
pii decr[maxn];

int n;

int add(int a,int b){
    return (a+b)%mod;
}

int mul(ll a,ll b){
    return a*b%mod;
}

int pwr(int a,int b){
    int ret=1;
    while(b){
        if(b&1) ret=mul(ret,a);
        b/=2;
        a=mul(a,a);
    }
    return ret;
}

pii comb(const pii a,const pii b){
    pii ret;
    if(a.xx==b.xx) ret={a.xx,add(a.yy,b.yy)};
    else ret=max(a,b);
    return ret;
}

void update(int t,pii v,pii *seg,int ind=1,int l=0,int r=n-1){
    if(l==r){
        seg[ind]=v;
        return;
    }
    int mid=l+(r-l)/2;
    if(t<=mid) update(t,v,seg,2*ind,l,mid);
    else update(t,v,seg,2*ind+1,mid+1,r);
    seg[ind]=comb(seg[2*ind],seg[2*ind+1]);
}

pii query(int tl,int tr,pii *seg,int ind=1,int l=0,int r=n-1){
    if(tl<=l && r<=tr) return seg[ind];
    int mid=l+(r-l)/2;
    pii ret={0,0};
    if(tl<=mid) ret=comb(ret,query(tl,tr,seg,2*ind,l,mid));
    if(tr>mid) ret=comb(ret,query(tl,tr,seg,2*ind+1,mid+1,r));
    return ret;
}

void solve(){
    cin>>n;
    ff(i,0,n){
        cin>>niz[i];
        compr[i]=niz[i];
    }
    sort(compr,compr+n);
    ff(i,0,n){
        niz[i]=lower_bound(compr,compr+n,niz[i])-compr;
    }
    fb(i,n,0){
        {//decr
            pii qry;
            if(niz[i]>0) qry=query(0,niz[i]-1,segdec);
            else qry={0,0};
            qry.xx++;
            qry=max(qry,mp(1,1));
            update(niz[i],qry,segdec);
            incr[i]=qry;
        }
        {//incr
            pii qry;
            if(niz[i]<n-1) qry=query(niz[i]+1,n-1,seginc);
            else qry={0,0};
            qry.xx++;
            qry=max(qry,mp(1,1));
            update(niz[i],qry,seginc);
            decr[i]=qry;
        }
    }
    pii res=mp(0,0);
    ff(i,0,n){
        pii tren={incr[i].xx+decr[i].xx-1,mul(incr[i].yy,decr[i].yy)};
        if(res.xx==tren.xx) res.yy=add(res.yy,tren.yy);
        else res=max(res,tren);
    }
    cout<<res.xx<<" "<<mul(res.yy,pwr(2,n-res.xx));
}

int main(){
    ios;
    int t=1;
//    cin>>t;
    while(t--) solve();
    return 0;
}

Compilation message (stderr)

zoltan.cpp: In function 'void solve()':
zoltan.cpp:9:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    9 | #define ff(i,s,f) for(int (i)=s;(i)<(f);(i)++)
      |                           ^
zoltan.cpp:89:5: note: in expansion of macro 'ff'
   89 |     ff(i,0,n){
      |     ^~
zoltan.cpp:9:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    9 | #define ff(i,s,f) for(int (i)=s;(i)<(f);(i)++)
      |                           ^
zoltan.cpp:94:5: note: in expansion of macro 'ff'
   94 |     ff(i,0,n){
      |     ^~
zoltan.cpp:10:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   10 | #define fb(i,s,f) for(int (i)=s-1;(i)>=f;(i)--)
      |                           ^
zoltan.cpp:97:5: note: in expansion of macro 'fb'
   97 |     fb(i,n,0){
      |     ^~
zoltan.cpp:9:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    9 | #define ff(i,s,f) for(int (i)=s;(i)<(f);(i)++)
      |                           ^
zoltan.cpp:118:5: note: in expansion of macro 'ff'
  118 |     ff(i,0,n){
      |     ^~

• Subtask 1: 112 / 140