oj.uz

Submission #996782

# Submission time Handle Problem Language Result Execution time Memory
996782 2024-06-11T08:08:32 Z Nika533 Zoltan (COCI16_zoltan) C++14
98 / 140
 319 ms 30288 KB 
#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

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.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4440 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 2 ms 4444 KB Output is correct
8 Correct 2 ms 4444 KB Output is correct
9 Correct 2 ms 4440 KB Output is correct
10 Correct 2 ms 4444 KB Output is correct
11 Incorrect 212 ms 27176 KB Output isn't correct
12 Incorrect 171 ms 25508 KB Output isn't correct
13 Incorrect 170 ms 20808 KB Output isn't correct
14 Incorrect 223 ms 25684 KB Output isn't correct
15 Incorrect 279 ms 28192 KB Output isn't correct
16 Incorrect 319 ms 30288 KB Output isn't correct
17 Correct 244 ms 28356 KB Output is correct
18 Correct 257 ms 28368 KB Output is correct
19 Correct 242 ms 28496 KB Output is correct
20 Correct 248 ms 28496 KB Output is correct