oj.uz

Submission #893035

# Submission time Handle Problem Language Result Execution time Memory
893035 2023-12-26T11:44:47 Z d4xn Abracadabra (CEOI22_abracadabra) C++17
10 / 100
 3000 ms 29780 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5, Q = 1e6;

int n, q, a[N], b[N], ans[Q];
tuple<int, int, int> qry[Q];

signed main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> n >> q;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  for (int i = 0; i < q; i++) {
    int x, y;
    cin >> x >> y;
    y--;
    qry[i] = make_tuple(x, y, i);
  }
  sort(qry, qry+q);

  int curr = 0;
  bool same = 0;
  for (int i = 0; i < q; i++) {
    //cerr << get<0>(qry[i]) << " " << get<1>(qry[i]) << " " << get<2>(qry[i]) << endl;
    while (!same && curr < get<0>(qry[i])) {
      curr++;

      int l = 0;
      int r = n/2;
      int x = 0;
      while (l < n/2 && r < n) {
        if (a[l] < a[r]) {
          b[x++] = a[l++];
        }
        else {
          b[x++] = a[r++];
        }
      }

      while (l < n/2) {
        b[x++] = a[l++];
      }

      while (r < n) {
        b[x++] = a[r++];
      }

      bool ok = 1;
      for (int i = 0; i < n; i++) {
        if (a[i] != b[i]) ok = 0;
        a[i] = b[i];
      }
      if (ok) same = 1;
    }
    ans[get<2>(qry[i])] = a[get<1>(qry[i])];
  }

  for (int i = 0; i < q; i++) {
    cout << ans[i] << "\n";
  }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 261 ms 28532 KB Output is correct
2 Correct 280 ms 28220 KB Output is correct
3 Correct 248 ms 27884 KB Output is correct
4 Correct 270 ms 26708 KB Output is correct
5 Correct 267 ms 27996 KB Output is correct
6 Correct 266 ms 26960 KB Output is correct
7 Correct 267 ms 28132 KB Output is correct
8 Correct 252 ms 27032 KB Output is correct
9 Correct 262 ms 26852 KB Output is correct
10 Correct 252 ms 27248 KB Output is correct
11 Correct 262 ms 26996 KB Output is correct
12 Correct 248 ms 26100 KB Output is correct
13 Correct 263 ms 26864 KB Output is correct
14 Correct 266 ms 27604 KB Output is correct
15 Correct 262 ms 27108 KB Output is correct
16 Correct 1 ms 4440 KB Output is correct
17 Correct 238 ms 26576 KB Output is correct
18 Correct 246 ms 26208 KB Output is correct
19 Correct 1 ms 4440 KB Output is correct
20 Correct 1 ms 4444 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3031 ms 29780 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3055 ms 8668 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 261 ms 28532 KB Output is correct
2 Correct 280 ms 28220 KB Output is correct
3 Correct 248 ms 27884 KB Output is correct
4 Correct 270 ms 26708 KB Output is correct
5 Correct 267 ms 27996 KB Output is correct
6 Correct 266 ms 26960 KB Output is correct
7 Correct 267 ms 28132 KB Output is correct
8 Correct 252 ms 27032 KB Output is correct
9 Correct 262 ms 26852 KB Output is correct
10 Correct 252 ms 27248 KB Output is correct
11 Correct 262 ms 26996 KB Output is correct
12 Correct 248 ms 26100 KB Output is correct
13 Correct 263 ms 26864 KB Output is correct
14 Correct 266 ms 27604 KB Output is correct
15 Correct 262 ms 27108 KB Output is correct
16 Correct 1 ms 4440 KB Output is correct
17 Correct 238 ms 26576 KB Output is correct
18 Correct 246 ms 26208 KB Output is correct
19 Correct 1 ms 4440 KB Output is correct
20 Correct 1 ms 4444 KB Output is correct
21 Execution timed out 3031 ms 29780 KB Time limit exceeded
22 Halted 0 ms 0 KB -