oj.uz

Submission #996761

# Submission time Handle Problem Language Result Execution time Memory
996761 2024-06-11T07:32:22 Z Nika533 Zoltan (COCI16_zoltan) C++14
28 / 140
 126 ms 65536 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],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);
     dp2[1]={1,1}; update(1,1,n,arr[1],dp2[1]);
     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]);
     }
     
     // dp1[1]={1,1}; update(1,1,n,arr[1],dp1[1]);
     // for (int i=2; i<=n; i++) {
     //      pii val=query(1,1,n,1,arr[i]-1); 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);
     // dp2[1]={1,1}; update(1,1,n,arr[1],dp2[1]);
     // for (int i=2; i<=n; i++) {
     //      pii val=query(1,1,n,arr[i]+1,n); 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};
     for (int i=1; i<=n; i++) {
          pii val=query(1,1,n,1,arr[i]-1); if (val.f==0) val.s=1;
          if (i==1) val={0,1};
          pii ans2; ans2.f=val.f+dp1[i].f; ans2.s=val.s*dp1[i].s;
          ans2.s*=power(2,n-ans2.f);
          ans=MAX(ans,ans2);

          // cout<<"I "<<i<<" "<<val.f<<" "<<val.s<<" "<<dp1[i].f<<" "<<dp1[i].s<<endl;
          // cout<<ans2.f<<" "<<ans2.s<<endl;
     }

     cout<<ans.f<<" "<<ans.s<<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:114:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  114 | main () {
      | ^~~~

Subtask #1
28.0 / 140.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 6492 KB Output isn't correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Incorrect 1 ms 6488 KB Output isn't correct
6 Correct 1 ms 6492 KB Output is correct
7 Incorrect 1 ms 6492 KB Output isn't correct
8 Incorrect 1 ms 6492 KB Output isn't correct
9 Incorrect 2 ms 6492 KB Output isn't correct
10 Incorrect 2 ms 6492 KB Output isn't correct
11 Runtime error 76 ms 36688 KB Execution killed with signal 11
12 Runtime error 64 ms 33484 KB Execution killed with signal 11
13 Runtime error 93 ms 65536 KB Execution killed with signal 9
14 Runtime error 84 ms 33620 KB Execution killed with signal 11
15 Runtime error 113 ms 38484 KB Execution killed with signal 11
16 Runtime error 126 ms 42320 KB Execution killed with signal 11
17 Runtime error 89 ms 38352 KB Execution killed with signal 11
18 Runtime error 94 ms 38476 KB Execution killed with signal 11
19 Runtime error 107 ms 38392 KB Execution killed with signal 11
20 Runtime error 92 ms 38484 KB Execution killed with signal 11