oj.uz

Submission #923149

# Submission time Handle Problem Language Result Execution time Memory
923149 2024-02-06T18:21:57 Z myst6 Zoltan (COCI16_zoltan) C++14
98 / 140
 159 ms 16080 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)

struct Info {
  int m, ct;
  Info(int M, int C) : m(M), ct(C) {}
  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);
    }
  }
};

using ll = long long;

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

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;
}

/*
100
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
*/

Subtask #1
98.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 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 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Incorrect 102 ms 12756 KB Output isn't correct
12 Incorrect 87 ms 10976 KB Output isn't correct
13 Incorrect 81 ms 10324 KB Output isn't correct
14 Incorrect 111 ms 11092 KB Output isn't correct
15 Incorrect 145 ms 13848 KB Output isn't correct
16 Incorrect 159 ms 15920 KB Output isn't correct
17 Correct 125 ms 16080 KB Output is correct
18 Correct 122 ms 15952 KB Output is correct
19 Correct 121 ms 16012 KB Output is correct
20 Correct 136 ms 15996 KB Output is correct