oj.uz

Submission #787228

# Submission time Handle Problem Language Result Execution time Memory
787228 2023-07-18T23:25:24 Z tvladm2009 Index (COCI21_index) C++17
110 / 110
 685 ms 9872 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = (int) 2e5 + 7;
const int BS = 448;
int a[N], aib[N];

void add(int i, int x) {
  while (i < N) {
    aib[i] += x;
    i += i & (-i);
  }
}

int get(int i) {
  int sol = 0;
  while (i) {
    sol += aib[i];
    i -= i & (-i);
  }
  return sol;
}

struct Query {
  int l;
  int r;
  int id;
};

bool operator < (Query a, Query b) {
  return a.l / BS < b.l / BS || (a.l / BS == b.l / BS && a.r < b.r);
}

Query queries[N];
int sol[N];
int n, q;

void expand(int x) {
  add(a[x], +1);
}

void contract(int x) {
  add(a[x], -1);
}

void Mo() {
  int l = 1, r = 0;
  for (int i = 1; i <= q; i++) {
    int ql = queries[i].l;
    int qr = queries[i].r;
    while (l > ql) {
      l--;
      expand(l);
    }
    while (r < qr) {
      r++;
      expand(r);
    }
    while (l < ql) {
      contract(l);
      l++;
    }
    while (r > qr) {
      contract(r);
      r--;
    }
    int low = 1, high = N - 1;
    while (low <= high) {
      int mid = (low + high) / 2;
      if ((qr - ql + 1) - get(mid - 1) >= mid) {
        low = mid + 1;
        sol[queries[i].id] = mid;
      } else {
        high = mid - 1;
      }
    }
  }
}

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

  // freopen("input", "r", stdin);

  cin >> n >> q;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  for (int i = 1; i <= q; i++) {
    cin >> queries[i].l >> queries[i].r;
    queries[i].id = i;
  }
  sort(queries + 1, queries + q + 1);
  Mo();
  for (int i = 1; i <= q; i++) {
    cout << sol[i] << "\n";
  }
  return 0;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 336 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 336 KB Output is correct
7 Correct 2 ms 336 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 121 ms 2592 KB Output is correct
12 Correct 119 ms 2596 KB Output is correct
13 Correct 124 ms 2596 KB Output is correct
14 Correct 119 ms 2596 KB Output is correct
15 Correct 123 ms 2608 KB Output is correct
16 Correct 120 ms 2636 KB Output is correct
17 Correct 136 ms 2668 KB Output is correct
18 Correct 120 ms 2636 KB Output is correct
19 Correct 119 ms 2596 KB Output is correct
20 Correct 119 ms 2596 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 336 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 336 KB Output is correct
7 Correct 2 ms 336 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 121 ms 2592 KB Output is correct
12 Correct 119 ms 2596 KB Output is correct
13 Correct 124 ms 2596 KB Output is correct
14 Correct 119 ms 2596 KB Output is correct
15 Correct 123 ms 2608 KB Output is correct
16 Correct 120 ms 2636 KB Output is correct
17 Correct 136 ms 2668 KB Output is correct
18 Correct 120 ms 2636 KB Output is correct
19 Correct 119 ms 2596 KB Output is correct
20 Correct 119 ms 2596 KB Output is correct
21 Correct 584 ms 9860 KB Output is correct
22 Correct 594 ms 9856 KB Output is correct
23 Correct 597 ms 9852 KB Output is correct
24 Correct 559 ms 9848 KB Output is correct
25 Correct 685 ms 9852 KB Output is correct
26 Correct 616 ms 9840 KB Output is correct
27 Correct 597 ms 9860 KB Output is correct
28 Correct 562 ms 9872 KB Output is correct
29 Correct 604 ms 9852 KB Output is correct
30 Correct 587 ms 9856 KB Output is correct