oj.uz

Submission #706666

# Submission time Handle Problem Language Result Execution time Memory
706666 2023-03-07T09:53:00 Z Pety Volontiranje (COCI21_volontiranje) C++14
0 / 110
 11 ms 23764 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 1e6+2;
int aib[N], dp[N], n, a[N];
vector<int>LIS[N];
void update (int x, int val) {
  for (int i = x; i <= n; i += (i & -i))
    aib[i] = max(aib[i],val);
}
int query (int x) {
  int s= 0;
  for (int i = x; i; i -= (i & -i))
    s = max(s, aib[i]);
  return s;
}

int main () 
{
  ios_base::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  cin >> n;
  int mx = 0;
  for (int i = 1; i <= n; i++) {
    int x;
    cin >> x;
    a[i] = x;
    dp[i] = query(x) + 1;
    update(x, dp[i]);
    LIS[dp[i]].push_back(i);
    mx = max(mx, dp[i]);
  }
  int cnt = LIS[1].size();
  reverse(LIS[1].begin(), LIS[1].end());
  for (int i = 2; i <= mx; i++) {
    int index = 0;
    vector<int>aux;
    for (int j = LIS[i].size() - 1; j >= 0; j--) {
      int i1 = LIS[i - 1][index];
      int j1 = LIS[i][j];
      if (i1 < j1 && a[i1] < a[j1]) {
        aux.push_back(j1);
        index++;
      }
    }
    cnt = index;
    LIS[i] = aux;
  }
  cout << cnt << " " << mx << "\n";
  for (int i =0 ; i < cnt; i++, cout << "\n")
    for (int j = 1; j <= mx; j++)
      cout << LIS[j][i] << " "; 
  return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 23764 KB Integer parameter [name=number of subsequences] equals to 0, violates the range [1, 7]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 23764 KB Integer parameter [name=number of subsequences] equals to 0, violates the range [1, 7]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 23764 KB Integer parameter [name=number of subsequences] equals to 0, violates the range [1, 7]
2 Halted 0 ms 0 KB -