Submission #1154752

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154752		zhehan	Index (COCI21_index)	C++20	0 / 110	2 ms	1088 KiB

index

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> ii;

int nsqrt;

vector<int> ft(2e5 + 5, 0);

void upd(int p, int v) {
  while (p < ft.size()) {
    ft[p] += v;
    p += p & (-p);
  }
}

int qry(int p) {
  int ans = 0;
  while (p > 0) {
    ans += ft[p];
    p -= p & (-p);
  }
  return ans;
}

int sufqry(int l) { return qry(ft.size() - 1) - qry(l - 1); }

bool cmp(ii a, ii b) {
  if (a.first / nsqrt == b.first / nsqrt) {
    return a.second < b.second;
  }
  return a.first < b.first;
}

int main() {
  int n, q;
  cin >> n >> q;
  nsqrt = pow(n, 0.5);
  vector<int> h(n, 0);
  for (int i = 0; i < n; ++i) {
    cin >> h[i];
  }
  vector<ii> oqueries(q, ii());
  for (int i = 0; i < q; ++i) {
    cin >> oqueries[i].first >> oqueries[i].second;
  }
  vector<ii> queries;
  map<ii, int> ans;
  for (auto e : oqueries) {
    queries.push_back({e.first - 1, e.second - 1});
  }
  sort(queries.begin(), queries.end(), cmp);
  int l = 0, r = -1, hind = 0;
  for (auto e : queries) {
    for (int i = r + 1; i <= e.second; ++i) {
      upd(h[i], 1);
      if (sufqry(hind + 1) >= hind + 1) {
        hind += 1;
      }
    }
    for (int i = e.second + 1; i <= r; ++i) {
      upd(h[i], -1);
      if (sufqry(hind) < hind) {
        hind -= 1;
      }
    }
    r = e.second;
    for (int i = l; i < e.first; ++i) {
      upd(h[i], -1);
      if (sufqry(hind) < hind) {
        hind -= 1;
      }
    }

    for (int i = e.first; i < l; ++i) {
      upd(h[i], 1);
      if (sufqry(hind + 1) < hind + 1) {
        hind += 1;
      }
    }
    l = e.first;
    ans[e] = hind;
  }
  for (auto e : oqueries) {
    cout << ans[{e.first - 1, e.second - 1}] << '\n';
  }
}

• Subtask 1: 0 / 20
• Subtask 2: 0 / 40
• Subtask 3: 0 / 50