oj.uz

Submission #1046958

# Submission time Handle Problem Language Result Execution time Memory
1046958 2024-08-07T06:54:10 Z vjudge1 Index (COCI21_index) C++17
110 / 110
 1937 ms 36352 KB 
#include <bits/stdc++.h>
using namespace std;

#define all(a) a.begin(), a.end()

struct segtr {
  vector<vector<int>> tree;
  int n;
  segtr(vector<int> const &a)
      : n(a.size()), tree(a.size() << 1, vector<int>()) {
    for (int i = 0; i < n; i++)
      tree[i + n].push_back(a[i]);
    for (int i = n - 1; i > 0; i--) {
      merge(all(tree[i << 1]), all(tree[i << 1 | 1]), back_inserter(tree[i]));
    }
  }
  int query(int l, int r, int h) {
    int res = 0;
    for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
      if (l & 1) {
        res += tree[l].end() - lower_bound(all(tree[l]), h);
        l++;
      }
      if (r & 1) {
        r--;
        res += tree[r].end() - lower_bound(all(tree[r]), h);
      }
    }
    return res;
  }
  int query(int l, int r) {
    int ll = 0, rr = r - l + 1;
    int ans = INT_MIN;
    while (rr - ll >= 0) {
      int m = (rr + ll) >> 1;
      if (query(l, r, m) >= m) {
        ans = max(ans, m);
        ll = m + 1;
      } else
        rr = m - 1;
    }
    return ans;
  }
};

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int n, q;
  cin >> n >> q;
  vector<int> a(n);
  for (auto &x : a)
    cin >> x;
  segtr tr(a);
  while (q--) {
    int l, r;
    cin >> l >> r;
    l--;
    r--;
    cout << tr.query(l, r) << '\n';
  }
}

Compilation message

index.cpp: In constructor 'segtr::segtr(const std::vector<int>&)':
index.cpp:8:7: warning: 'segtr::n' will be initialized after [-Wreorder]
    8 |   int n;
      |       ^
index.cpp:7:23: warning:   'std::vector<std::vector<int> > segtr::tree' [-Wreorder]
    7 |   vector<vector<int>> tree;
      |                       ^~~~
index.cpp:9:3: warning:   when initialized here [-Wreorder]
    9 |   segtr(vector<int> const &a)
      |   ^~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 2 ms 604 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 2 ms 348 KB Output is correct
10 Correct 2 ms 604 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 2 ms 604 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 2 ms 348 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 311 ms 9048 KB Output is correct
12 Correct 318 ms 9052 KB Output is correct
13 Correct 316 ms 9048 KB Output is correct
14 Correct 312 ms 8912 KB Output is correct
15 Correct 320 ms 9044 KB Output is correct
16 Correct 313 ms 8908 KB Output is correct
17 Correct 321 ms 8912 KB Output is correct
18 Correct 318 ms 8912 KB Output is correct
19 Correct 318 ms 9040 KB Output is correct
20 Correct 316 ms 8912 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 2 ms 604 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 2 ms 348 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 311 ms 9048 KB Output is correct
12 Correct 318 ms 9052 KB Output is correct
13 Correct 316 ms 9048 KB Output is correct
14 Correct 312 ms 8912 KB Output is correct
15 Correct 320 ms 9044 KB Output is correct
16 Correct 313 ms 8908 KB Output is correct
17 Correct 321 ms 8912 KB Output is correct
18 Correct 318 ms 8912 KB Output is correct
19 Correct 318 ms 9040 KB Output is correct
20 Correct 316 ms 8912 KB Output is correct
21 Correct 1937 ms 36320 KB Output is correct
22 Correct 1927 ms 36332 KB Output is correct
23 Correct 1903 ms 36264 KB Output is correct
24 Correct 1907 ms 36280 KB Output is correct
25 Correct 1911 ms 36296 KB Output is correct
26 Correct 1931 ms 36308 KB Output is correct
27 Correct 1931 ms 36332 KB Output is correct
28 Correct 1900 ms 36248 KB Output is correct
29 Correct 1892 ms 36352 KB Output is correct
30 Correct 1920 ms 36284 KB Output is correct