oj.uz

Submission #923150

# Submission time Handle Problem Language Result Execution time Memory
923150 2024-02-06T18:29:17 Z myst6 Zoltan (COCI16_zoltan) C++14
140 / 140
 194 ms 15992 KB 
#include <bits/stdc++.h>

using namespace std;

// put all numbers left-to-right
// and get M and C(ount)
// can move any selection of the N-M numbers across for each of the C seqs
// so ans = C * 2^(N-M)

using ll = long long;

const ll mod = 1'000'000'007LL;

struct Info {
  int m, ct;
  Info(int M, int C) : m(M), ct(C%mod) {}
  Info() : Info(0, 0) {}
  Info combine(Info &other) {
    if (m == other.m) return {m, ct + other.ct};
    else if (m > other.m) return {m, ct};
    else return {other.m, other.ct};  
  }
};

struct Tree {
  vector<Info> info;
  Tree(int size) { info.resize(size*4); }
  void update(int v, int x, int xl, int xr, Info delta) {
    if (xl == xr) {
      info[x] = delta;
    } else {
      int xm = (xl + xr) / 2;
      if (v <= xm) update(v, x*2, xl, xm, delta);
      else update(v, x*2+1, xm+1, xr, delta);
      info[x] = info[x*2].combine(info[x*2+1]);
    }
  }
  Info query(int l, int r, int x, int xl, int xr) {
    if (l > r) return {};
    if (l == xl && r == xr) {
      return info[x];
    } else {
      int xm = (xl + xr) / 2;
      Info left = query(l, min(r, xm), x*2, xl, xm);
      Info right = query(max(l, xm+1), r, x*2+1, xm+1, xr);
      return left.combine(right);
    }
  }
};

ll modmul(ll a, ll b) {
  return a * b % mod;
}

ll modpow(ll a, ll b) {
  if (b == 0) return 1;
  if (b == 1) return a;
  ll half = modpow(a, b/2);
  ll ans = modmul(half, half);
  if (b % 2) return modmul(ans, a);
  else return ans;
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int N;
  cin >> N;
  vector<int> X(N);
  for (int i=0; i<N; i++) cin >> X[i];

  // find longest increasing subsequence starting at node 'i' 
  vector<int> order(N);
  iota(order.begin(), order.end(), 0);
  sort(order.begin(), order.end(), [&](int i, int j) -> bool { 
    if (X[i] == X[j]) return i < j;
    return X[i] > X[j]; 
  });
  Tree tree(N);
  vector<Info> incr(N);
  for (int i : order) {
    Info info = tree.query(i+1, N-1, 1, 0, N-1);
    info.m += 1;
    if (info.m == 1) info.ct = 1; // start once
    tree.update(i, 1, 0, N-1, info);
    incr[i] = info;
  }

  // find longest decreasing subsequence starting at node 'i'
  tree = Tree(N);
  sort(order.begin(), order.end(), [&](int i, int j) -> bool { 
    if (X[i] == X[j]) return i < j;
    return X[i] < X[j]; 
  });
  vector<Info> decr(N);
  for (int i : order) {
    Info info = tree.query(i+1, N-1, 1, 0, N-1);
    info.m += 1;
    if (info.m == 1) info.ct = 1; // start once
    tree.update(i, 1, 0, N-1, info);
    decr[i] = info;
  }

  Info best;
  for (int i=0; i<N; i++) {
    Info here = {
      decr[i].m + incr[i].m - 1,
      (int) modmul(decr[i].ct, incr[i].ct),
    };
    best = best.combine(here);
  }

  int M = best.m, C = best.ct;
  cout << M << " " << modmul(C, modpow(2, N-M)) << "\n";

  return 0;
}

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 504 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 344 KB Output is correct
11 Correct 127 ms 12624 KB Output is correct
12 Correct 104 ms 10976 KB Output is correct
13 Correct 96 ms 10364 KB Output is correct
14 Correct 126 ms 11092 KB Output is correct
15 Correct 164 ms 13616 KB Output is correct
16 Correct 194 ms 15956 KB Output is correct
17 Correct 150 ms 15956 KB Output is correct
18 Correct 169 ms 15984 KB Output is correct
19 Correct 154 ms 15952 KB Output is correct
20 Correct 150 ms 15992 KB Output is correct