oj.uz

Submission #682629

# Submission time Handle Problem Language Result Execution time Memory
682629 2023-01-16T16:03:37 Z Alex_tz307 Index (COCI21_index) C++17
110 / 110
 2396 ms 132852 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 2e5;
 
struct node {
  node *l;
  node *r;
  int sum;
 
  node() : sum(0) {
    l = nullptr;
    r = nullptr;
  }
} *roots[1 + N];
 
void build(node *root, int lx, int rx) {
  if (lx == rx) {
    return;
  }
 
  int mid = (lx + rx) / 2;
 
  root->l = new node;
  build(root->l, lx, mid);
 
  root->r = new node;
  build(root->r, mid + 1, rx);
}
 
void update(node *prevRoot, node *root, int lx, int rx, int pos, int val) {
  if (lx == rx) {
    root->sum = prevRoot->sum + val;
    return;
  }
 
  int mid = (lx + rx) / 2;
 
  if (pos <= mid) {
    root->l = new node;
 
    root->r = prevRoot->r;
 
    update(prevRoot->l, root->l, lx, mid, pos, val);
  } else {
    root->l = prevRoot->l;
 
    root->r = new node;
 
    update(prevRoot->r, root->r, mid + 1, rx, pos, val);
  }
 
  root->sum = root->l->sum + root->r->sum;
}
 
int query(node *root, int lx, int rx, int st, int dr) {
  if (st <= lx && rx <= dr) {
    return root->sum;
  }
 
  int mid = (lx + rx) / 2;
 
  int sum = 0;
 
  if (st <= mid) {
    sum += query(root->l, lx, mid, st, dr);
  }
 
  if (mid < dr) {
    sum += query(root->r, mid + 1, rx, st, dr);
  }
 
  return sum;
}
 
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
 
  int n, q;
  cin >> n >> q;
 
  roots[0] = new node;
  build(roots[0], 1, N);
 
  for (int i = 1; i <= n; ++i) {
    int x;
    cin >> x;
 
    roots[i] = new node;
    update(roots[i - 1], roots[i], 1, N, x, 1);
  }
 
  for (int i = 0; i < q; ++i) {
    int l, r;
    cin >> l >> r;
 
    int st = 2, dr = r - l + 1, res = 1;
 
    while (st <= dr) {
      int mid = (st + dr) / 2;
 
      if (query(roots[r], 1, N, mid, N) - query(roots[l - 1], 1, N, mid, N) >= 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 17 ms 13396 KB Output is correct
2 Correct 17 ms 13432 KB Output is correct
3 Correct 23 ms 13392 KB Output is correct
4 Correct 17 ms 13432 KB Output is correct
5 Correct 16 ms 13396 KB Output is correct
6 Correct 20 ms 13404 KB Output is correct
7 Correct 17 ms 13348 KB Output is correct
8 Correct 16 ms 13396 KB Output is correct
9 Correct 19 ms 13396 KB Output is correct
10 Correct 23 ms 13436 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 13396 KB Output is correct
2 Correct 17 ms 13432 KB Output is correct
3 Correct 23 ms 13392 KB Output is correct
4 Correct 17 ms 13432 KB Output is correct
5 Correct 16 ms 13396 KB Output is correct
6 Correct 20 ms 13404 KB Output is correct
7 Correct 17 ms 13348 KB Output is correct
8 Correct 16 ms 13396 KB Output is correct
9 Correct 19 ms 13396 KB Output is correct
10 Correct 23 ms 13436 KB Output is correct
11 Correct 282 ms 42676 KB Output is correct
12 Correct 289 ms 42684 KB Output is correct
13 Correct 321 ms 42768 KB Output is correct
14 Correct 292 ms 42724 KB Output is correct
15 Correct 329 ms 42908 KB Output is correct
16 Correct 285 ms 42800 KB Output is correct
17 Correct 312 ms 42732 KB Output is correct
18 Correct 282 ms 42676 KB Output is correct
19 Correct 295 ms 42752 KB Output is correct
20 Correct 294 ms 42864 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 13396 KB Output is correct
2 Correct 17 ms 13432 KB Output is correct
3 Correct 23 ms 13392 KB Output is correct
4 Correct 17 ms 13432 KB Output is correct
5 Correct 16 ms 13396 KB Output is correct
6 Correct 20 ms 13404 KB Output is correct
7 Correct 17 ms 13348 KB Output is correct
8 Correct 16 ms 13396 KB Output is correct
9 Correct 19 ms 13396 KB Output is correct
10 Correct 23 ms 13436 KB Output is correct
11 Correct 282 ms 42676 KB Output is correct
12 Correct 289 ms 42684 KB Output is correct
13 Correct 321 ms 42768 KB Output is correct
14 Correct 292 ms 42724 KB Output is correct
15 Correct 329 ms 42908 KB Output is correct
16 Correct 285 ms 42800 KB Output is correct
17 Correct 312 ms 42732 KB Output is correct
18 Correct 282 ms 42676 KB Output is correct
19 Correct 295 ms 42752 KB Output is correct
20 Correct 294 ms 42864 KB Output is correct
21 Correct 2007 ms 132752 KB Output is correct
22 Correct 2125 ms 132852 KB Output is correct
23 Correct 2114 ms 132640 KB Output is correct
24 Correct 2150 ms 132720 KB Output is correct
25 Correct 2323 ms 132536 KB Output is correct
26 Correct 2375 ms 132580 KB Output is correct
27 Correct 2396 ms 132620 KB Output is correct
28 Correct 2162 ms 132568 KB Output is correct
29 Correct 2104 ms 132664 KB Output is correct
30 Correct 2101 ms 132604 KB Output is correct