Submission #1147043

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147043		omtheprogrammer1	Curtains (NOI23_curtains)	C++20	0 / 100	7 ms	12104 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() {
  ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
  freopen("error.txt", "w", stderr);
  int tc = 1;
  // cin >> tc;
  FOR(i, 0, tc, 1) solve(i);
}

Compilation message (stderr)

curtains.cpp: In function 'int main()':
curtains.cpp:114:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |   freopen("input.txt", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
curtains.cpp:115:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  115 |   freopen("output.txt", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
curtains.cpp:116:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  116 |   freopen("error.txt", "w", stderr);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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