oj.uz

Submission #793927

# Submission time Handle Problem Language Result Execution time Memory
793927 2023-07-26T08:09:26 Z ind1v Index (COCI21_index) C++11
110 / 110
 488 ms 41780 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 200005;

struct fenwick_tree {
  int fenw[N];
  
  fenwick_tree() {
    memset(fenw, 0, sizeof(fenw));
  }
  
  void reset() {
    memset(fenw, 0, sizeof(fenw));
  }
  
  void upd(int idx, int val) {
    for (; idx < N; idx |= (idx + 1)) {
      fenw[idx] += val;
    }
  }
  
  int get(int idx) {
    int res = 0;
    for (; idx >= 0; idx &= (idx + 1), --idx) {
      res += fenw[idx];
    }
    return res;
  }
  
  int get(int l, int r) {
    return get(r) - get(l - 1);
  }
};

int n, q;
int p[N];
int l[N], r[N];
int x[N], y[N], ans[N];
vector<int> cand[N], pos[N];
fenwick_tree ft;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> q;
  for (int i = 1; i <= n; i++) {
    cin >> p[i];
    pos[p[i]].emplace_back(i);
  }
  for (int i = 1; i <= q; i++) {
    cin >> l[i] >> r[i];
    x[i] = 1;
    y[i] = 200000;
    ans[i] = -1;
  }
  for (int ite = 1; ite <= 20; ite++) {
    ft.reset();
    for (int i = 1; i <= 200000; i++) {
      cand[i].clear();
    }
    for (int i = 1; i <= q; i++) {
      if (x[i] > y[i]) {
        continue;
      }
      cand[x[i] + y[i] >> 1].emplace_back(i);
    }
    for (int i = 200000; i >= 1; i--) {
      for (int &idx : pos[i]) {
        ft.upd(idx, +1);
      }
      for (int &que : cand[i]) {
        if (ft.get(l[que], r[que]) >= i) {
          ans[que] = i;
          x[que] = i + 1;
        } else {
          y[que] = i - 1;
        }
      }
    }
  }
  for (int i = 1; i <= q; i++) {
    cout << ans[i] << '\n';
  }
  return 0;
}

Compilation message

index.cpp: In function 'int main()':
index.cpp:67:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   67 |       cand[x[i] + y[i] >> 1].emplace_back(i);
      |            ~~~~~^~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 10624 KB Output is correct
2 Correct 19 ms 10580 KB Output is correct
3 Correct 20 ms 10640 KB Output is correct
4 Correct 19 ms 10628 KB Output is correct
5 Correct 17 ms 10668 KB Output is correct
6 Correct 19 ms 10628 KB Output is correct
7 Correct 20 ms 10652 KB Output is correct
8 Correct 24 ms 10580 KB Output is correct
9 Correct 23 ms 10644 KB Output is correct
10 Correct 19 ms 10580 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 10624 KB Output is correct
2 Correct 19 ms 10580 KB Output is correct
3 Correct 20 ms 10640 KB Output is correct
4 Correct 19 ms 10628 KB Output is correct
5 Correct 17 ms 10668 KB Output is correct
6 Correct 19 ms 10628 KB Output is correct
7 Correct 20 ms 10652 KB Output is correct
8 Correct 24 ms 10580 KB Output is correct
9 Correct 23 ms 10644 KB Output is correct
10 Correct 19 ms 10580 KB Output is correct
11 Correct 101 ms 18008 KB Output is correct
12 Correct 98 ms 17956 KB Output is correct
13 Correct 113 ms 18008 KB Output is correct
14 Correct 116 ms 18208 KB Output is correct
15 Correct 100 ms 17952 KB Output is correct
16 Correct 109 ms 17932 KB Output is correct
17 Correct 99 ms 18012 KB Output is correct
18 Correct 97 ms 18064 KB Output is correct
19 Correct 111 ms 18056 KB Output is correct
20 Correct 111 ms 17992 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 10624 KB Output is correct
2 Correct 19 ms 10580 KB Output is correct
3 Correct 20 ms 10640 KB Output is correct
4 Correct 19 ms 10628 KB Output is correct
5 Correct 17 ms 10668 KB Output is correct
6 Correct 19 ms 10628 KB Output is correct
7 Correct 20 ms 10652 KB Output is correct
8 Correct 24 ms 10580 KB Output is correct
9 Correct 23 ms 10644 KB Output is correct
10 Correct 19 ms 10580 KB Output is correct
11 Correct 101 ms 18008 KB Output is correct
12 Correct 98 ms 17956 KB Output is correct
13 Correct 113 ms 18008 KB Output is correct
14 Correct 116 ms 18208 KB Output is correct
15 Correct 100 ms 17952 KB Output is correct
16 Correct 109 ms 17932 KB Output is correct
17 Correct 99 ms 18012 KB Output is correct
18 Correct 97 ms 18064 KB Output is correct
19 Correct 111 ms 18056 KB Output is correct
20 Correct 111 ms 17992 KB Output is correct
21 Correct 409 ms 41468 KB Output is correct
22 Correct 414 ms 41488 KB Output is correct
23 Correct 426 ms 41556 KB Output is correct
24 Correct 419 ms 41412 KB Output is correct
25 Correct 481 ms 41616 KB Output is correct
26 Correct 452 ms 41508 KB Output is correct
27 Correct 427 ms 41284 KB Output is correct
28 Correct 438 ms 41780 KB Output is correct
29 Correct 452 ms 41380 KB Output is correct
30 Correct 488 ms 41276 KB Output is correct