oj.uz

Submission #864473

# Submission time Handle Problem Language Result Execution time Memory
864473 2023-10-23T03:59:39 Z NeroZein Zoltan (COCI16_zoltan) C++17
7 / 140
 160 ms 9044 KB 
#include "bits/stdc++.h"
using namespace std;

#ifdef Nero
#include "Deb.h"
#else
#define deb(...)
#endif

const int N = 2e5 + 5;
const int md = (int) 1e9 + 7; 

int a[N], p2[N]; 
pair<int, int> seg[N * 2];
pair<int, int> lis[N], lds[N]; 

void add(int& x, int y) {
  x += y;
  if (x >= md) x -= md;
}

int mul(int x, int y) {
  return (int) ((long long) x * y % md); 
}

pair<int, int> comb(pair<int,int> x, pair<int,int> y) {
  if (x.first == y.first) {
    return {x.first, x.second + y.second};
  }
  return max(x, y); 
}

void upd(int nd, int l, int r, int p, pair<int, int> v) {
  if (l == r) {
    seg[nd] = v; 
    return;
  }
  int mid = (l + r) >> 1;
  int rs = nd + ((mid - l + 1) << 1);
  if (p <= mid) {
    upd(nd + 1, l, mid, p, v);
  } else {
    upd(rs, mid + 1, r, p, v); 
  }
  seg[nd] = comb(seg[nd + 1], seg[rs]); 
}

pair<int, int> qry(int nd, int l, int r, int s, int e) {
  if (l >= s && r <= e) {
    return seg[nd];
  }
  int mid = (l + r) >> 1;
  int rs = nd + ((mid - l + 1) << 1);
  if (mid >= e) {
    return qry(nd + 1, l, mid, s, e); 
  } else {
    if (mid < s) {
      return qry(rs, mid + 1, r, s, e); 
    } else {
      return comb(qry(nd + 1, l, mid, s, e), qry(rs, mid + 1, r, s, e)); 
    }
  }
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  p2[0] = 1;
  for (int i = 1; i < N; ++i) {
    p2[i] = mul(p2[i - 1], 2); 
  }
  int n;
  cin >> n;
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
  }
  vector<int> id(n);
  iota(id.begin(), id.end(), 0);
  sort(id.begin(), id.end(), [&](int i, int j) {
    return a[i] == a[j] ? i < j : a[i] > a[j]; 
  });
  for (int i = 0; i < n; ++i) {
    int ind = id[i];
    lis[ind] = qry(0, 0, n, ind, n);
    lis[ind].first++; 
    if (lis[ind].second == 0) {
      lis[ind].second = 1; 
    }
    upd(0, 0, n - 1, ind, lis[ind]); 
  }
  for (int i = 0; i < N * 2; ++i) {
    seg[i] = {0, 0}; 
  }
  sort(id.begin(), id.end(), [&](int i, int j) {
    return a[i] == a[j] ? i < j : a[i] < a[j]; 
  });
  int mx = 1; 
  for (int i = 0; i < n; ++i) {
    int ind = id[i];
    lds[ind] = qry(0, 0, n, ind, n);
    lds[ind].first++;
    if (lds[ind].second == 0) {
      lds[ind].second = 1; 
    }
    upd(0, 0, n - 1, ind, lds[ind]); 
    mx = max(mx, lis[ind].first + lds[ind].first - 1); 
  }
  int cnt = 0; 
  for (int i = 0; i < n; ++i) {
    if (lis[i].first + lds[i].first == mx + 1) {
      add(cnt, mul(p2[n - mx], mul(lis[i].second, lds[i].second)));
    }
  }
  cout << mx << ' ' << cnt << '\n'; 
  return 0;
}

Subtask #1
7.0 / 140.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 6232 KB Output isn't correct
2 Incorrect 3 ms 6236 KB Output isn't correct
3 Incorrect 2 ms 6236 KB Output isn't correct
4 Correct 2 ms 6252 KB Output is correct
5 Incorrect 2 ms 6236 KB Output isn't correct
6 Incorrect 2 ms 6236 KB Output isn't correct
7 Incorrect 3 ms 6236 KB Output isn't correct
8 Incorrect 3 ms 6236 KB Output isn't correct
9 Incorrect 4 ms 6236 KB Output isn't correct
10 Incorrect 3 ms 6236 KB Output isn't correct
11 Incorrect 98 ms 8676 KB Output isn't correct
12 Incorrect 83 ms 8412 KB Output isn't correct
13 Incorrect 80 ms 8284 KB Output isn't correct
14 Incorrect 105 ms 8020 KB Output isn't correct
15 Incorrect 132 ms 8524 KB Output isn't correct
16 Incorrect 160 ms 8876 KB Output isn't correct
17 Incorrect 121 ms 8888 KB Output isn't correct
18 Incorrect 124 ms 8884 KB Output isn't correct
19 Incorrect 133 ms 9036 KB Output isn't correct
20 Incorrect 121 ms 9044 KB Output isn't correct