Submission #1148794

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148794		LinkedArray	Curtains (NOI23_curtains)	C++17	100 / 100	486 ms	68916 KiB

curtains

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

using ll = long long;
#define pb push_back

const int INF = 1e9;
const int MAX_N = 5e5;

struct SegTree {
  int segTree[4 * MAX_N + 4];

  void init (int n) {
    for (int v = 1; v <= 4 * n; v++) {
      segTree[v] = INF;
    }
  }

  void update (int v, int l, int r, int lu, int ru) {
    if (l > ru || r < lu) {
      return;
    }

    if (lu <= l && r <= ru) {
      segTree[v] = min(segTree[v], ru);
      return;
    }

    int mid = (l + r) / 2;
    update(2 * v + 1, l, mid, lu, ru);
    update(2 * v + 2, mid + 1, r, lu, ru);
    segTree[v] = min(segTree[v], max(segTree[2 * v + 1], segTree[2 * v + 2]));
  }

  void update (int l, int r, int n) {
    update(0, 0, n, l, r);
  }

  int query (int v, int l, int r, int lq, int rq) {
    if (l > rq || r < lq) {
      return 1;
    }

    if (lq <= l && r <= rq) {
      return (segTree[v] <= rq);
    }

    int mid = (l + r) / 2;
    return query(2 * v + 1, l, mid, lq, rq) &&
           query(2 * v + 2, mid + 1, r, lq, rq);
  }

  int query (int l, int r, int n) {
    return query(0, 0, n, l, r);
  }
};

SegTree aint;
vector<int> l, r, s, e, rasp;
vector<vector<int>> ints_starting_at, queries_starting_at;

int main () {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, m, q, i, starting_at;

  cin >> n >> m >> q;

  l = vector<int>(m + 1);
  r = vector<int>(m + 1);
  ints_starting_at = vector<vector<int>>(n + 1);
  for (i = 1; i <= m; i++) {
    cin >> l[i] >> r[i];
    ints_starting_at[l[i]].push_back(i);
  }

  s = vector<int>(q + 1);
  e = vector<int>(q + 1);
  queries_starting_at = vector<vector<int>>(n + 1);
  for (i = 1; i <= q; i++) {
    cin >> s[i] >> e[i];
    queries_starting_at[s[i]].push_back(i);
  }

  for (starting_at = 1; starting_at <= n; starting_at++) {
    sort(ints_starting_at[starting_at].begin(),
         ints_starting_at[starting_at].end(),
         [&] (int ints1_idx, int ints2_idx) {
           int ints1_ends_at = r[ints1_idx];
           int ints2_ends_at = r[ints2_idx];
           return ints1_ends_at < ints1_ends_at;
         });

    sort(queries_starting_at[starting_at].begin(),
         queries_starting_at[starting_at].end(),
         [&] (int queries1_idx, int queries2_idx) {
           int queries1_ends_at = e[queries1_idx];
           int queries2_ends_at = e[queries2_idx];
           return queries1_ends_at < queries2_ends_at;
         });
  }

  rasp = vector<int>(q + 1);
  aint.init(n);
  for (starting_at = n; starting_at >= 1; starting_at--) {
    for (auto ints_idx : ints_starting_at[starting_at]) {
      int ints_ends_at = r[ints_idx];
      aint.update(starting_at, ints_ends_at, n);
    }
    for (auto queries_idx : queries_starting_at[starting_at]) {
      int queries_ends_at = e[queries_idx];
      rasp[queries_idx] = aint.query(starting_at, queries_ends_at, n);
    }
  }

  for (i = 1; i <= q; i++) {
    if (rasp[i]) {
      cout << "YES\n";
      continue;
    }

    cout << "NO\n";
  }
  return 0;
}

• Subtask 1: 3 / 3
• Subtask 2: 6 / 6
• Subtask 3: 15 / 15
• Subtask 4: 20 / 20
• Subtask 5: 36 / 36
• Subtask 6: 20 / 20