oj.uz

Submission #362393

# Submission time Handle Problem Language Result Execution time Memory
362393 2021-02-02T23:06:30 Z vkgainz Zoltan (COCI16_zoltan) C++17
21 / 140
 719 ms 49772 KB 
#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.0 / 140.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 5100 KB Output isn't correct
2 Incorrect 4 ms 5100 KB Output isn't correct
3 Incorrect 4 ms 5120 KB Output isn't correct
4 Correct 4 ms 5100 KB Output is correct
5 Correct 4 ms 5100 KB Output is correct
6 Correct 4 ms 5100 KB Output is correct
7 Incorrect 6 ms 5356 KB Output isn't correct
8 Incorrect 5 ms 5356 KB Output isn't correct
9 Incorrect 5 ms 5356 KB Output isn't correct
10 Incorrect 5 ms 5356 KB Output isn't correct
11 Runtime error 379 ms 40300 KB Memory limit exceeded
12 Runtime error 320 ms 35564 KB Memory limit exceeded
13 Runtime error 312 ms 33900 KB Memory limit exceeded
14 Runtime error 472 ms 36332 KB Memory limit exceeded
15 Runtime error 612 ms 43632 KB Memory limit exceeded
16 Runtime error 719 ms 49772 KB Memory limit exceeded
17 Runtime error 507 ms 44952 KB Memory limit exceeded
18 Runtime error 503 ms 44908 KB Memory limit exceeded
19 Runtime error 495 ms 45036 KB Memory limit exceeded
20 Runtime error 502 ms 44968 KB Memory limit exceeded