oj.uz

Submission #893053

# Submission time Handle Problem Language Result Execution time Memory
893053 2023-12-26T12:22:35 Z d4xn Abracadabra (CEOI22_abracadabra) C++17
10 / 100
 3000 ms 25220 KB 
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math,inline")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,lzcnt,mmx,abm,avx,avx2,fma")
#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++) {
    while (!same && curr < get<0>(qry[i])) {
      curr++;

      int L = 0;
      bool bL = 1;

      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++];
          if (bL) L++;
        }
        else {
          bL = 0;
          b[x++] = a[r++];
        }
      }

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

      bool ok = 1;
      for (int i = L; i < r; 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 325 ms 25220 KB Output is correct
2 Correct 334 ms 24900 KB Output is correct
3 Correct 316 ms 24704 KB Output is correct
4 Correct 320 ms 24036 KB Output is correct
5 Correct 338 ms 24640 KB Output is correct
6 Correct 311 ms 24548 KB Output is correct
7 Correct 331 ms 24912 KB Output is correct
8 Correct 316 ms 24436 KB Output is correct
9 Correct 318 ms 24404 KB Output is correct
10 Correct 316 ms 24488 KB Output is correct
11 Correct 317 ms 24452 KB Output is correct
12 Correct 306 ms 23892 KB Output is correct
13 Correct 325 ms 24148 KB Output is correct
14 Correct 321 ms 24708 KB Output is correct
15 Correct 328 ms 24404 KB Output is correct
16 Correct 1 ms 4444 KB Output is correct
17 Correct 307 ms 23940 KB Output is correct
18 Correct 322 ms 23892 KB Output is correct
19 Correct 1 ms 4444 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 3095 ms 23176 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 3051 ms 8276 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 325 ms 25220 KB Output is correct
2 Correct 334 ms 24900 KB Output is correct
3 Correct 316 ms 24704 KB Output is correct
4 Correct 320 ms 24036 KB Output is correct
5 Correct 338 ms 24640 KB Output is correct
6 Correct 311 ms 24548 KB Output is correct
7 Correct 331 ms 24912 KB Output is correct
8 Correct 316 ms 24436 KB Output is correct
9 Correct 318 ms 24404 KB Output is correct
10 Correct 316 ms 24488 KB Output is correct
11 Correct 317 ms 24452 KB Output is correct
12 Correct 306 ms 23892 KB Output is correct
13 Correct 325 ms 24148 KB Output is correct
14 Correct 321 ms 24708 KB Output is correct
15 Correct 328 ms 24404 KB Output is correct
16 Correct 1 ms 4444 KB Output is correct
17 Correct 307 ms 23940 KB Output is correct
18 Correct 322 ms 23892 KB Output is correct
19 Correct 1 ms 4444 KB Output is correct
20 Correct 1 ms 4444 KB Output is correct
21 Execution timed out 3095 ms 23176 KB Time limit exceeded
22 Halted 0 ms 0 KB -