제출 #1147044

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1147044		omtheprogrammer1	Curtains (NOI23_curtains)	C++20	100 / 100	1139 ms	57316 KiB

curtains

#include<bits/stdc++.h>

using namespace std;

#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")

#define ordered_set tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>
#define ll long long
#define pii pair<ll,ll>
#define mp make_pair
#define f first
#define s second
#define FOR(i,j,n,k) for(int i = j;((k>0)?(i<n):(i>n));i+=k)
#define pb push_back
#define all(x) x.begin(),x.end()
#define siz(x) (int)sizeof(x)

ll n, m, k, q, l, r, x, y, z;
const ll tas = 5e5 + 10;
ll a[tas];
vector<int> grid[tas];
string s;
ll ans[tas];

ll t[4 * tas];

void push(int i, int l, int r) {
  if (t[2 * i + 1] < t[i]) {
    t[2 * i + 1] = t[i];
  }
  if (t[2 * i + 2] < t[i]) {
    t[2 * i + 2] = t[i];
  }
}

ll check(ll x, ll y) {
  if (x == -1)return y;
  if (y == -1) return x;
  return min(x, y);
}

void update(int i, int l, int r, int tl, int tr, ll val) {
  if (r < tl || tr < l) {
    return;
  }
  if (tl <= l && r <= tr) {
    t[i] = max(t[i], val);
    // cout << i << " " << t[i] << endl;
    return;
  }
  push(i, l, r);
  int mid = (l + r) / 2;
  update(2 * i + 1, l, mid, tl, tr, val);
  update(2 * i + 2, mid + 1, r, tl, tr, val);
  t[i] = check(t[2 * i + 1], t[2 * i + 2]);
}

ll query(int i, int l, int r, int tl, int tr) {
  // cout << r << endl;
  if (r < tl || tr < l) {
    return 1e12;
  }
  if (tl <= l && r <= tr) {
    // cout << l << " " << t[i] << endl;
    return t[i];
  }
  push(i, l, r);
  int mid = (l + r) / 2;
  return min(query(2 * i + 1, l, mid, tl, tr),
             query(2 * i + 2, mid + 1, r, tl, tr));

}

void solve(int tc = 0) {
  cin >> n >> m >> q;
  FOR(i, 0, 4 * n, 1)t[i] = -1e12;
  vector<pair<int, pii>> vec;
  FOR(i, 0, m, 1) {
    cin >> l >> r;
    l--, r--;
    vec.pb(mp(r, mp(0, l)));
  }
  FOR(i, 0, q, 1) {
    cin >> l >> r;
    l--, r--;
    // cout << i + 1 << endl;
    vec.pb(mp(r, mp(i + 1, l)));
  }
  sort(all(vec));
  for (auto val : vec) {
    l = val.s.s, r = val.f;
    // cout << val.s.f << endl;
    if (val.s.f == 0) {
      update(0, 0, n - 1, l, r, l);
    }
    else {
      // cout << query(0, 0, n - 1, l, r) << " " << l << endl;
      ans[val.s.f - 1] = (query(0, 0, n - 1, l, r) >= l && 1e10 > query(0, 0, n - 1, l, r));
    }
  }
  // FOR(i, 0, n, 1) cout << i << " " << query(0, 0, n - 1, i, i) << endl;
  FOR(i, 0, q, 1) if (ans[i]) cout << "YES" << endl;
  else cout << "NO" << endl;
}

int main() {

  int tc = 1;
  // cin >> tc;
  FOR(i, 0, tc, 1) solve(i);
}

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