Submission #1136547

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136547		duckindog	Curtains (NOI23_curtains)	C++17	100 / 100	686 ms	62340 KiB

curtains

#include <bits/stdc++.h>

using namespace std;  

const int N = 500'000 + 10;
int n, m, q;

vector<pair<int, int>> saveSeg[N];
vector<tuple<int, int, int>> saveQuery[N];

namespace IT { 
  int f[N << 2], lazy[N << 2];
  void push(int s) { 
    f[s << 1] = max(f[s << 1], lazy[s]);
    f[s << 1 | 1] = max(f[s << 1 | 1], lazy[s]);

    lazy[s << 1] = max(lazy[s << 1], lazy[s]);
    lazy[s << 1 | 1] = max(lazy[s << 1 | 1], lazy[s]);
  }
  void update(int s, int l, int r, int u, int v, int x) { 
    if (v < l || u > r) return;
    if (u <= l && r <= v) { 
      f[s] = max(f[s], x);
      lazy[s] = max(lazy[s], x);
      return;
    }
    push(s);
    int mid = (l + r) >> 1;
    update(s << 1, l, mid, u, v, x); update(s << 1 | 1, mid + 1, r, u, v, x);
    f[s] = min(f[s << 1], f[s << 1 | 1]);
  }
  int query(int s, int l, int r, int u, int v) { 
    if (v < l || u > r) return 1'000'000'000;
    if (u <= l && r <= v) return f[s];
    push(s);
    int mid = (l + r) >> 1;
    return min(query(s << 1, l, mid, u, v), query(s << 1 | 1, mid + 1, r, u, v));
  }
}

int32_t main() {
  cin.tie(0)->sync_with_stdio(0);

  cin >> n >> m >> q;
  for (int i = 1; i <= m; ++i) { 
    int l, r; cin >> l >> r;
    saveSeg[r].push_back({l, r});
  }
  for (int i = 1; i <= q; ++i) { 
    int l, r; cin >> l >> r;
    saveQuery[r].emplace_back(l, r, i);
  }

  vector<int> answer(q + 1);
  for (int i = 1; i <= n; ++i) { 
    for (auto [l, r] : saveSeg[i])
      IT::update(1, 1, n, l, r, l);
    
    for (auto [l, r, idx] : saveQuery[i]) 
      answer[idx] = (IT::query(1, 1, n, l, r) >= l);
  }

  for (int i = 1; i <= q; ++i) 
    cout << (answer[i] ? "YES" : "NO") << "\n";
}

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