Submission #362393

#	Time	Username	Problem	Language	Result	Execution time	Memory
362393		vkgainz	Zoltan (COCI16_zoltan)	C++17	21 / 140	719 ms	49772 KiB

zoltan

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int MX = 2e5 + 5;
ll mod = 1000000007;
int segDown[2*MX];
int segUp[2*MX];
ll numDown[2*MX];
ll numUp[2*MX];
int dpDown[MX], dpUp[MX];
ll dpNumDown[MX], dpNumUp[MX];
int n;
void upd(int i, int v, bool b) {
  i+=n;
  if(b) segUp[i] = v;
  else segDown[i] = v;
  while(i>1) {
    i/=2;
    if(b) segUp[i] = max(segUp[2*i], segUp[2*i+1]);
    else segDown[i] = max(segDown[2*i], segDown[2*i+1]);
  }
}
int query(int l, int r, bool b) {
  l+=n, r+=n;
  int ans = 0;
  while(l<r) {
    if(l%2) {
      if(b) ans = max(ans, segUp[l++]);
      else ans = max(ans, segDown[l++]);
    }
    if(r%2) {
      if(b) ans = max(ans, segUp[--r]);
      else ans = max(ans, segDown[--r]);
    }
    l/=2, r/=2;
  }
  return ans;
}
void updNum(int i, ll v, bool b) {
  i+=n;
  if(b) numUp[i] += v, numUp[i]%=mod;
  else numDown[i] += v, numDown[i]%=mod;
  while(i>1) {
    i/=2;
    if(b) numUp[i] = numUp[2*i] + numUp[2*i+1], numUp[i]%=mod;
    else numDown[i] = numDown[2*i] + numDown[2*i+1], numDown[i]%=mod;
  }
}
ll queryNum(int l, int r, bool b) {
  l+=n, r+=n;
  ll ans = 0;
  while(l<r) {
    if(l%2) {
      if(b) ans += numUp[l++];
      else ans += numDown[l++];
    }
    if(r%2) {
      if(b) ans += numUp[--r];
      else ans += numDown[--r];
    }
    ans%=mod, l/=2, r/=2;
  }
  return ans;
}
void compress(vector<int> &a) {
    set<int> s;
    for(int i=0;i<n;i++) s.insert(a[i]);
    map<int,int> m;
    int v = 0;
    for(auto &it : s) {
        m[it] = v++;
    }
    for(int i=0;i<n;i++) a[i] = m[a[i]];
}
int dp[200001];
vector<int> ord[200001];
int main() {
    cin >> n;
    vector<int> a(n);
    for(int i=0;i<n;i++) cin >> a[i];
    compress(a);
    vector<int> upIn[n+1], downIn[n+1];
    for(int i=n-1;i>=0;i--) {
      int x = query(a[i]+1, n, 1) + 1;
      int y = query(0, a[i], 0) + 1;
      dpUp[i] = x, dpDown[i] = y;
      upd(a[i], dpUp[i], 1);
      upd(a[i], dpDown[i], 0);
      upIn[dpUp[i]].push_back(i);
      downIn[dpDown[i]].push_back(i);
    }
    for(int i=1;i<=n;i++) {
      for(int x : upIn[i]) {
        if(dpUp[x] == 1) dpNumUp[x] = 1LL;
        else {
          dpNumUp[x] = queryNum(a[x] + 1, n, 1);
        }
      }
      for(int x : upIn[i-1]) {
        updNum(a[x], -dpNumUp[x], 1);
      }
      for(int x : upIn[i]) {
        updNum(a[x], dpNumUp[x], 1);
      }
    }
    for(int i=1;i<=n;i++) {
      for(int x : downIn[i]) {
        if(dpDown[x] == 1) dpNumDown[x] = 1LL;
        else {
          dpNumDown[x] = queryNum(0, a[x], 0);
        }
      }
      for(int x : downIn[i-1]) {
        updNum(a[x], -dpNumDown[x], 0);
      }
      for(int x : downIn[i]) {
        updNum(a[x], dpNumDown[x], 0);
      }
    }
    int mx = 0;
    ll ans = 0LL;
    for(int i=0;i<n;i++) {
      if(dpDown[i] + dpUp[i] - 1 > mx) {
        mx = dpDown[i] + dpUp[i] - 1;
        ans = (dpNumDown[i]*1LL*dpNumUp[i])%mod;
      }
      else if(dpDown[i] + dpUp[i] - 1 == mx) {
        ans += (dpNumDown[i]*1LL*dpNumUp[i])%mod;
      }
    }
    ll x = 1LL;
    for(int i=0;i<n-mx;i++) x *= 2, x%=mod;
    ans*=x;
    ans%=mod;
    if(ans<0) ans+=mod;
    cout << mx << " " << ans << "\n";
}

• Subtask 1: 21 / 140