oj.uz

Submission #864470

# Submission time Handle Problem Language Result Execution time Memory
864470 2023-10-23T03:53:17 Z NeroZein Zoltan (COCI16_zoltan) C++17
98 / 140
 274 ms 18260 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;
  map<int, int> mp; 
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
    mp[a[i]];
  }
  int cnt = 0;
  for (auto& it : mp) {
    it.second = cnt++; 
  }
  for (int i = 0; i < n; ++i) {
    a[i] = mp[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]; 
  });
  upd(0, 0, n, n, {0, 1}); 
  for (int i = 0; i < n; ++i) {
    int ind = id[i];
    lis[ind] = qry(0, 0, n, ind, n);
    lis[ind].first++; 
    upd(0, 0, n, 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; 
  upd(0, 0, n, n, {0, 1}); 
  for (int i = 0; i < n; ++i) {
    int ind = id[i];
    lds[ind] = qry(0, 0, n, ind, n);
    lds[ind].first++;
    upd(0, 0, n, ind, lds[ind]); 
    mx = max(mx, lis[ind].first + lds[ind].first - 1); 
  }
  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(lds[i].second, lis[i].second)));
    }
  }
  cout << mx << ' ' << cnt << '\n'; 
  return 0;
}

Subtask #1
98.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7260 KB Output is correct
2 Correct 2 ms 7328 KB Output is correct
3 Correct 2 ms 7260 KB Output is correct
4 Correct 2 ms 7260 KB Output is correct
5 Correct 2 ms 7260 KB Output is correct
6 Correct 2 ms 7260 KB Output is correct
7 Correct 3 ms 7260 KB Output is correct
8 Correct 3 ms 7260 KB Output is correct
9 Correct 3 ms 7260 KB Output is correct
10 Correct 3 ms 7260 KB Output is correct
11 Incorrect 183 ms 15728 KB Output isn't correct
12 Incorrect 145 ms 14300 KB Output isn't correct
13 Incorrect 130 ms 13908 KB Output isn't correct
14 Incorrect 170 ms 14476 KB Output isn't correct
15 Incorrect 244 ms 16816 KB Output isn't correct
16 Incorrect 274 ms 18260 KB Output isn't correct
17 Correct 185 ms 16804 KB Output is correct
18 Correct 181 ms 16700 KB Output is correct
19 Correct 179 ms 16844 KB Output is correct
20 Correct 175 ms 16752 KB Output is correct