oj.uz

Submission #960105

# Submission time Handle Problem Language Result Execution time Memory
960105 2024-04-09T16:28:56 Z Pety Volontiranje (COCI21_volontiranje) C++14
0 / 110
 757 ms 524288 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 1e6+2;
int aib[N], dp[N], n, a[N];
set<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]].insert(i);
    mx = max(mx, dp[i]);
  }
  vector<vector<int>>ans;
  while (1) {
    bool ok = 1;
    int last = *LIS[mx].begin();
    LIS[mx].erase(last);
    vector<int>sir;
    sir.push_back(last);
    for (int i = mx - 1; i >= 1; i--) {
      bool gasit = 0;
      for (auto it : LIS[i]) {
        if (it < last && a[it] < a[last]) {
          last = it;
          sir.push_back(last);
          gasit = 1;
          break;
        }
      }
      LIS[i].erase(last);
      if (!gasit) {ok = 0; break;}
    }
    if (!ok) break;
    reverse(sir.begin(), sir.end());
    ans.push_back(sir);
  }
  cout << ans.size() << " " << ans[0].size() << "\n";
  for (auto s : ans) {
    for (auto it : s)
      cout << it << " ";
    cout << "\n";
  }
  return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 47196 KB Output is correct
2 Correct 16 ms 47452 KB Output is correct
3 Correct 17 ms 47452 KB Output is correct
4 Correct 17 ms 47280 KB Output is correct
5 Correct 18 ms 47440 KB Output is correct
6 Correct 17 ms 47452 KB Output is correct
7 Runtime error 757 ms 524288 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 47196 KB Output is correct
2 Correct 16 ms 47452 KB Output is correct
3 Correct 17 ms 47452 KB Output is correct
4 Correct 17 ms 47280 KB Output is correct
5 Correct 18 ms 47440 KB Output is correct
6 Correct 17 ms 47452 KB Output is correct
7 Runtime error 757 ms 524288 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 47196 KB Output is correct
2 Correct 16 ms 47452 KB Output is correct
3 Correct 17 ms 47452 KB Output is correct
4 Correct 17 ms 47280 KB Output is correct
5 Correct 18 ms 47440 KB Output is correct
6 Correct 17 ms 47452 KB Output is correct
7 Runtime error 757 ms 524288 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -