oj.uz

Submission #682615

# Submission time Handle Problem Language Result Execution time Memory
682615 2023-01-16T15:29:07 Z vjudge1 Index (COCI21_index) C++17
60 / 110
 2500 ms 35036 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 2e5;
const int INF = 1e9;
vector<pair<int, int>> aib[1 + N];

void build() {
  for (int i = 1; i <= N; ++i) {
    aib[i].emplace_back(0, 0);
  }
}

void update(int version, int p, int v) {
  for (int i = p; i <= N; i += i & -i) {
    aib[i].emplace_back(version, aib[i].back().second + v);
  }
}

int query(int version, int p) {
  int res = 0;

  for (int i = p; i > 0; i = i & (i - 1)) {
    auto it = upper_bound(aib[i].begin(), aib[i].end(), make_pair(version, INF)) - 1;
    res += it->second;
  }

  return res;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, q;
  cin >> n >> q;

  build();

  for (int i = 1; i <= n; ++i) {
    int x;
    cin >> x;

    update(i, x, 1);
  }

  for (int i = 0; i < q; ++i) {
    int l, r;
    cin >> l >> r;

    int len = r - l + 1;

    int st = 2, dr = len, res = 1;

    while (st <= dr) {
      int mid = (st + dr) / 2;

      if (len - (query(r, mid - 1) - query(l - 1, mid - 1)) >= mid) {
        res = mid;
        st = mid + 1;
      } else {
        dr = mid - 1;
      }
    }

    cout << res << '\n';
  }

  return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 11348 KB Output is correct
2 Correct 13 ms 11348 KB Output is correct
3 Correct 14 ms 11384 KB Output is correct
4 Correct 13 ms 11348 KB Output is correct
5 Correct 13 ms 11348 KB Output is correct
6 Correct 14 ms 11432 KB Output is correct
7 Correct 20 ms 11432 KB Output is correct
8 Correct 13 ms 11432 KB Output is correct
9 Correct 14 ms 11348 KB Output is correct
10 Correct 18 ms 11296 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 11348 KB Output is correct
2 Correct 13 ms 11348 KB Output is correct
3 Correct 14 ms 11384 KB Output is correct
4 Correct 13 ms 11348 KB Output is correct
5 Correct 13 ms 11348 KB Output is correct
6 Correct 14 ms 11432 KB Output is correct
7 Correct 20 ms 11432 KB Output is correct
8 Correct 13 ms 11432 KB Output is correct
9 Correct 14 ms 11348 KB Output is correct
10 Correct 18 ms 11296 KB Output is correct
11 Correct 542 ms 17724 KB Output is correct
12 Correct 536 ms 17700 KB Output is correct
13 Correct 565 ms 17704 KB Output is correct
14 Correct 521 ms 17880 KB Output is correct
15 Correct 557 ms 17816 KB Output is correct
16 Correct 557 ms 17772 KB Output is correct
17 Correct 538 ms 17716 KB Output is correct
18 Correct 526 ms 17672 KB Output is correct
19 Correct 554 ms 17576 KB Output is correct
20 Correct 573 ms 17676 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 11348 KB Output is correct
2 Correct 13 ms 11348 KB Output is correct
3 Correct 14 ms 11384 KB Output is correct
4 Correct 13 ms 11348 KB Output is correct
5 Correct 13 ms 11348 KB Output is correct
6 Correct 14 ms 11432 KB Output is correct
7 Correct 20 ms 11432 KB Output is correct
8 Correct 13 ms 11432 KB Output is correct
9 Correct 14 ms 11348 KB Output is correct
10 Correct 18 ms 11296 KB Output is correct
11 Correct 542 ms 17724 KB Output is correct
12 Correct 536 ms 17700 KB Output is correct
13 Correct 565 ms 17704 KB Output is correct
14 Correct 521 ms 17880 KB Output is correct
15 Correct 557 ms 17816 KB Output is correct
16 Correct 557 ms 17772 KB Output is correct
17 Correct 538 ms 17716 KB Output is correct
18 Correct 526 ms 17672 KB Output is correct
19 Correct 554 ms 17576 KB Output is correct
20 Correct 573 ms 17676 KB Output is correct
21 Execution timed out 2566 ms 35036 KB Time limit exceeded
22 Halted 0 ms 0 KB -