oj.uz

답안 #866542

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
866542 2023-10-26T10:44:59 Z nima_aryan Zoltan (COCI16_zoltan) C++17
98 / 140
 260 ms 18192 KB 
/**
 *    author:  NimaAryan
 *    created: 2023-10-26 10:49:24  
**/
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "algo/debug.h"
#endif

using i64 = long long;

constexpr i64 M = 1E9 + 7;
void add(i64& x, i64 y) {
  if ((x += y) >= M) {
    x -= M;
  }
}

struct Info {
  int max_lis;
  i64 sum = 0;
};
Info operator+(Info a, Info b) {
  if (a.max_lis == b.max_lis) {
    return {a.max_lis, a.sum + b.sum};
  }
  return a.max_lis > b.max_lis ? a : b;
}

struct SegmentTree {
  vector<Info> info;
  int n;

  SegmentTree(int n) : n(n) {
    info.assign(4 << __lg(n), Info());
  }

  void modify(int p, int l, int r, int x, Info v) {
    if (r - l == 1) {
      info[p] = info[p] + v;
      return;
    }
    int m = (l + r) / 2;
    if (x < m) {
      modify(2 * p, l, m, x, v);
    } else {
      modify(2 * p + 1, m, r, x, v);
    }
    info[p] = info[2 * p] + info[2 * p + 1];
  }
  void modify(int x, Info v) {
    modify(1, 0, n, x, v);
  }

  Info query(int p, int l, int r, int lx, int rx) {
    if (l >= rx || r <= lx) {
      return Info();
    }
    if (l >= lx && r <= rx) {
      return info[p];
    }
    int m = (l + r) / 2;
    return query(2 * p, l, m, lx, rx) +
           query(2 * p + 1, m, r, lx, rx);
  }
  Info query(int lx, int rx) {
    return query(1, 0, n, lx, rx);
  }
};

auto LIS(vector<int> A) {
  auto B = A;
  sort(B.begin(), B.end());
  int n = A.size();
  for (int i = 0; i < n; ++i) {
    A[i] = lower_bound(B.begin(), B.end(), A[i]) - B.begin();
  }
  SegmentTree seg(n + 1);
  seg.modify(n, Info{0, 1});
  vector<int> lis(n);
  vector<i64> cnt(n);
  for (int i = n - 1; i >= 0; --i) {
    Info best = seg.query(A[i] + 1, n + 1);
    lis[i] = best.max_lis + 1;
    cnt[i] = best.sum;
    seg.modify(A[i], Info{lis[i], cnt[i]});
  }
  return pair(lis, cnt);
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int N;
  cin >> N;
  vector<int> A(N);
  for (int i = 0; i < N; ++i) {
    cin >> A[i];
  }
  auto [lis, cnt_lis] = LIS(A);
  for (int i = 0; i < N; ++i) {
    A[i] *= -1;
  }
  auto [lds, cnt_lds] = LIS(A);
  int best = 0;
  for (int i = 0; i < N; ++i) {
    best = max(best, lis[i] + lds[i] - 1);
  }
  i64 pow2 = 1;
  int p = 0;
  while (p < N - best) {
    pow2 = (pow2 * 2) % M;
    p += 1;
  }
  i64 cnt = 0;
  for (int i = 0; i < N; ++i) {
    if (lis[i] + lds[i] - 1 == best) {
      add(cnt, cnt_lis[i] * cnt_lds[i] % M * pow2 % M);
    }
  }
  cout << best << " " << cnt << "\n";
  return 0;
}

Subtask #1
98.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Incorrect 161 ms 15948 KB Output isn't correct
12 Incorrect 139 ms 15052 KB Output isn't correct
13 Incorrect 135 ms 10452 KB Output isn't correct
14 Incorrect 172 ms 15084 KB Output isn't correct
15 Incorrect 218 ms 16516 KB Output isn't correct
16 Incorrect 260 ms 17976 KB Output isn't correct
17 Correct 201 ms 18008 KB Output is correct
18 Correct 224 ms 17980 KB Output is correct
19 Correct 209 ms 18192 KB Output is correct
20 Correct 209 ms 17888 KB Output is correct