Submission #520375

#	Time	Username	Problem	Language	Result	Execution time	Memory
520375		Alex_tz307	Osumnjičeni (COCI21_osumnjiceni)	C++17	110 / 110	655 ms	39612 KiB

Main

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f

using namespace std;

struct node {
  int val, lazy;
};

void minSelf(int &x, const int &y) {
  if (y < x) {
    x = y;
  }
}

struct ST {
  vector<node> t;

  ST(int n) {
    int dim = 1;
    while (dim < n) {
      dim <<= 1;
    }
    t.resize(dim << 1, {INF, INF});
  }

  void push(int x) {
    if (t[x].lazy == INF) {
      return;
    }
    for (int i = 0; i < 2; ++i) {
      t[x << 1 | i] = {t[x].lazy, t[x].lazy};
    }
    t[x].lazy = INF;
  }

  void update(int x, int lx, int rx, int st, int dr, int val) {
    if (st <= lx && rx <= dr) {
      t[x] = {val, val};
      return;
    }
    push(x);
    int mid = (lx + rx) >> 1;
    if (st <= mid) {
      update(x << 1, lx, mid, st, dr, val);
    }
    if (mid < dr) {
      update(x << 1 | 1, mid + 1, rx, st, dr, val);
    }
    t[x].val = min(t[x << 1].val, t[x << 1 | 1].val);
  }

  int query(int x, int lx, int rx, int st, int dr) {
    if (st <= lx && rx <= dr) {
      return t[x].val;
    }
    push(x);
    int mid = (lx + rx) >> 1, ans = INF;
    if (st <= mid) {
      minSelf(ans, query(x << 1, lx, mid, st, dr));
    }
    if (mid < dr) {
      minSelf(ans, query(x << 1 | 1, mid + 1, rx, st, dr));
    }
    return ans;
  }
};

void TestCase() {
  int n;
  cin >> n;
  vector<int> st(n + 1), dr(n + 1), points;
  for (int i = 1; i <= n; ++i) {
    cin >> st[i] >> dr[i];
    points.emplace_back(st[i]);
    points.emplace_back(dr[i]);
  }
  sort(points.begin(), points.end());
  points.erase(unique(points.begin(), points.end()), points.end());
  auto getIndex = [&](const int &x) -> int {
    return upper_bound(points.begin(), points.end(), x) - points.begin();
  };
  for (int i = 1; i <= n; ++i) {
    st[i] = getIndex(st[i]);
    dr[i] = getIndex(dr[i]);
  }
  int m = points.size();
  points.clear();
  vector<int> lg2(n + 1);
  for (int i = 2; i <= n; ++i) {
    lg2[i] = lg2[i >> 1] + 1;
  }
  vector<vector<int>> nxt(n + 1, vector<int>(lg2[n] + 1, INF));
  ST t(m);
  for (int i = n; i > 0; --i) {
    nxt[i][0] = t.query(1, 1, m, st[i], dr[i]);
    t.update(1, 1, m, st[i], dr[i], i);
    if (i < n) {
      minSelf(nxt[i][0], nxt[i + 1][0]);
    }
  }
  for (int j = 1; j <= lg2[n]; ++j) {
    for (int i = 1; i <= n; ++i) {
      if (nxt[i][j - 1] != INF) {
        nxt[i][j] = nxt[nxt[i][j - 1]][j - 1];
      }
    }
  }
  int q;
  cin >> q;
  for (int i = 1; i <= q; ++i) {
    int l, r;
    cin >> l >> r;
    int ans = 0;
    for (int jump = lg2[r - l]; jump >= 0; --jump) {
      if (nxt[l][jump] <= r) {
        ans += (1 << jump);
        l = nxt[l][jump];
      }
    }
    cout << ans + 1 << '\n';
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int tests = 1;
  for (int tc = 1; tc <= tests; ++tc) {
    TestCase();
  }
  return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 50 / 50