oj.uz

Submission #996765

# Submission time Handle Problem Language Result Execution time Memory
996765 2024-06-11T07:35:53 Z Nika533 Zoltan (COCI16_zoltan) C++14
28 / 140
 297 ms 30548 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);
     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]);
     }

     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%MOD)*(dp1[i].s%MOD))%MOD;
          ans2.s*=power(2,n-ans2.f); ans2.s%=MOD;
          ans=MAX(ans,ans2);
     }

     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:96:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   96 | main () {
      | ^~~~

Subtask #1
28.0 / 140.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4444 KB Output isn't correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 0 ms 4444 KB Output is correct
5 Incorrect 0 ms 4444 KB Output isn't correct
6 Correct 1 ms 4444 KB Output is correct
7 Incorrect 2 ms 4668 KB Output isn't correct
8 Incorrect 1 ms 4444 KB Output isn't correct
9 Incorrect 2 ms 4440 KB Output isn't correct
10 Incorrect 1 ms 4444 KB Output isn't correct
11 Incorrect 187 ms 27220 KB Output isn't correct
12 Incorrect 152 ms 25688 KB Output isn't correct
13 Incorrect 154 ms 20752 KB Output isn't correct
14 Incorrect 229 ms 25568 KB Output isn't correct
15 Incorrect 261 ms 28240 KB Output isn't correct
16 Incorrect 297 ms 30548 KB Output isn't correct
17 Incorrect 232 ms 28500 KB Output isn't correct
18 Incorrect 212 ms 28496 KB Output isn't correct
19 Incorrect 242 ms 28556 KB Output isn't correct
20 Incorrect 222 ms 28496 KB Output isn't correct