Submission #996782

#	Time	Username	Problem	Language	Result	Execution time	Memory
996782		Nika533	Zoltan (COCI16_zoltan)	C++14	98 / 140	319 ms	30288 KiB

zoltan

#pragma gcc diagnostic "-std=c++1z"
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define f first
#define s second
#define MOD 1000000007
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define allr(x) (x).rbegin(),(x).rend()
using namespace std;
const int N=2e5+5;
int n,m,T,k,arr[N];
pii t[N*4],dp1[N],dp2[N];

int power(int a, int b) {
     int res=1;
     while (b) {
          if (b%2) {
               res=(res*a)%MOD;
          }
          a=(a*a)%MOD; b/=2;
     }
     return res;
}

pii MAX(pii a, pii b) {
     if (a.f!=b.f) return max(a,b);
     return {a.f,a.s+b.s};
}

void build(int v, int tl, int tr) {
     if (tl==tr) {
          t[v]={0,0};
          return;
     }
     int mid=(tl+tr)/2;
     build(v*2,tl,mid); build(v*2+1,mid+1,tr);
     t[v]=MAX(t[v*2],t[v*2+1]);
}
void update(int v, int tl, int tr, int ind, pii val) {
     if (tl==tr) {
          t[v]=MAX(t[v],val);
          return;
     }
     int mid=(tl+tr)/2;
     if (ind<=mid) update(v*2,tl,mid,ind,val);
     else update(v*2+1,mid+1,tr,ind,val);
     t[v]=MAX(t[v*2],t[v*2+1]);
}
pii query(int v, int tl, int tr, int l, int r) {
     if (l>r) return {0,0};
     if (tl==l && tr==r) return t[v];
     int mid=(tl+tr)/2;
     return MAX(query(v*2,tl,mid,l,min(mid,r)),query(v*2+1,mid+1,tr,max(l,mid+1),r));
}

void test_case() {
     cin>>n;

     int arr2[n+1]; map<int,int> IND;
     for (int i=1; i<=n; i++) {
          cin>>arr[i];
          arr2[i]=arr[i];
     }
     sort(arr2+1,arr2+1+n);
     for (int i=1; i<=n; i++) IND[arr2[i]]=i;
     for (int i=1; i<=n; i++) arr[i]=IND[arr[i]];

     build(1,1,n);
     for (int i=n; i>=1; i--) {
          pii val=query(1,1,n,arr[i]+1,n); if (val.f==0) val.s=1;
          dp1[i]={val.f+1,val.s};
          update(1,1,n,arr[i],dp1[i]);
     }

     build(1,1,n);
     for (int i=n; i>=1; i--) {
          pii val=query(1,1,n,1,arr[i]-1); if (val.f==0) val.s=1;
          dp2[i]={val.f+1,val.s};
          update(1,1,n,arr[i],dp2[i]);
     }

     pii ans={0,0};
     build(1,1,n);
     for (int i=2; i<=n; i++) {
          pii val=query(1,1,n,1,arr[i]-1); if (val.f==0) val.s=1;
          pii ans2; ans2.f=val.f+dp1[i].f; ans2.s=((val.s%MOD)*(dp1[i].s%MOD))%MOD;
          ans2.s*=power(2,n-ans2.f); ans2.s%=MOD;
          ans=MAX(ans,ans2);
          // cout<<"I "<<i<<" "<<val.f<<" "<<val.s<<" "<<dp1[i].f<<" "<<dp1[i].s<<endl;
          // cout<<ans2.f<<" "<<ans2.s<<endl;
          update(1,1,n,arr[i],dp2[i]);
     }

     pii mx1={0,1},mx2={0,1};
     for (int i=2; i<=n; i++) {
          if (arr[i]<arr[1]) mx2=MAX(mx2,dp2[i]);
          else if (arr[i]>arr[1]) mx1=MAX(mx1,dp1[i]);
     }
     pii val={mx1.f+mx2.f+1,((mx1.s%MOD)*(mx2.s%MOD))%MOD}; val.s*=power(2,n-val.f); val.s%=MOD;

     ans.s%=MOD; ans=MAX(ans,val);

     // for (int i=1; i<=n; i++) cout<<arr[i]<<" "; cout<<endl;
     // cout<<val.f<<" "<<val.s<<endl;

     cout<<ans.f<<" "<<ans.s%MOD<<endl;
}
main () {
	ios :: sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	T=1; 
	while (T--) test_case();
}

Compilation message (stderr)

zoltan.cpp:1: warning: ignoring '#pragma gcc diagnostic' [-Wunknown-pragmas]
    1 | #pragma gcc diagnostic "-std=c++1z"
      | 
zoltan.cpp:110:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  110 | main () {
      | ^~~~

• Subtask 1: 98 / 140