This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
//#include "bits_stdc++.h"
#include <stdio.h>
#include <algorithm>
#include <memory.h>
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define input(x) scanf("%lld", &x);
#define print(x, y) printf("%lld%c", x, y);
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ld, ll> pd;
typedef pair<string, ll> psl;
typedef pair<ll, ll> pi;
typedef pair<pi, ll> pii;
ll n, m, q, l ,r;
ll const INF = 1e13;
vector<vector<ll> > leftt, rightt;
vector<pii> queries;
vector<bool> ans;
vector<ll> toright, toleft;
void dnc(ll from, ll to, vector<pii> queries)
{
show2(from, to);
vector<pii> leftone, rightone;
if (queries.empty()) return;
if (from==to)
{
bool pos = false;
for (ll u: rightt[from]) if (u==to) {pos=true; break;}
for (pii u: queries) ans[u.s] = pos;
return;
}
ll mid = (from+to)/2;
toright.clear(); toleft.clear();
deque<pi> que;// (val, i)
for (ll i = mid; i>=from; i--)
{
ll aftermid = INF;
toright[i] = INF;
ll befmid = -INF;
for (ll u: rightt[i])
{
if (u>to) continue;
if (u>=mid) aftermid = min(aftermid, u);
else befmid = max(befmid, u);
}
toright[i] = min(toright[i], aftermid);
while (que.size() && (que.back().s<=befmid+1 || que.back().f>=toright[i]))
{
toright[i] = min(toright[i], que.back().f);
que.pop_back();
}
show2(i, toright[i]);
que.push_back(mp(toright[i], i));
show3(i, aftermid, befmid);
}
que.clear();
for (ll i = mid+1; i<=to; i++)
{
ll aftermid = -INF;
toleft[i] = -INF;
ll befmid = INF;
for (ll u: leftt[i])
{
if (u<from) continue;
if (u<=mid+1) aftermid = max(aftermid, u);
else befmid = min(befmid, u);
}
toleft[i] = max(toleft[i], aftermid);
while (que.size() && (que.back().s>=befmid-1 || que.back().f<=toleft[i]))
{
toleft[i] = max(toleft[i], que.back().f);
que.pop_back();
}
que.push_back(mp(toleft[i], i));
show2(i, toleft[i]);
show3(i, aftermid, befmid);
}
for (pii u: queries)
{
if (u.f.f <mid && u.f.s>mid)
{
ans[u.s] = (toright[u.f.f]<=u.f.s && toleft[u.f.s]>=u.f.f);
}
else if (u.f.s <= mid)
{
leftone.pb(u);
}
else
{
rightone.pb(u);
}
}
dnc(from, mid, leftone);
dnc(mid+1, to, rightone);
}
int main()
{
input(n); input(m); input(q);
leftt.resize(n+1); rightt.resize(n+1);
toleft.resize(n+1); toright.resize(n+1);
ans.resize(q);
for (ll i=0; i<m; ++i)
{
input(l); input(r);
leftt[r].pb(l);
rightt[l].pb(r);
}
for (ll i=0; i<q; ++i)
{
input(l); input(r);
queries.pb(mp(mp(l, r), i));
}
dnc(1, n, queries);
for (ll i=0; i<q; ++i)
{
if (ans[i]) cout << "YES" << endl;
else cout << "NO" << endl;
}
return 0;
}
Compilation message (stderr)
curtains.cpp: In function 'int main()':
curtains.cpp:12:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
12 | #define input(x) scanf("%lld", &x);
| ~~~~~^~~~~~~~~~~~
curtains.cpp:110:2: note: in expansion of macro 'input'
110 | input(n); input(m); input(q);
| ^~~~~
curtains.cpp:12:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
12 | #define input(x) scanf("%lld", &x);
| ~~~~~^~~~~~~~~~~~
curtains.cpp:110:12: note: in expansion of macro 'input'
110 | input(n); input(m); input(q);
| ^~~~~
curtains.cpp:12:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
12 | #define input(x) scanf("%lld", &x);
| ~~~~~^~~~~~~~~~~~
curtains.cpp:110:22: note: in expansion of macro 'input'
110 | input(n); input(m); input(q);
| ^~~~~
curtains.cpp:12:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
12 | #define input(x) scanf("%lld", &x);
| ~~~~~^~~~~~~~~~~~
curtains.cpp:116:3: note: in expansion of macro 'input'
116 | input(l); input(r);
| ^~~~~
curtains.cpp:12:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
12 | #define input(x) scanf("%lld", &x);
| ~~~~~^~~~~~~~~~~~
curtains.cpp:116:13: note: in expansion of macro 'input'
116 | input(l); input(r);
| ^~~~~
curtains.cpp:12:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
12 | #define input(x) scanf("%lld", &x);
| ~~~~~^~~~~~~~~~~~
curtains.cpp:122:3: note: in expansion of macro 'input'
122 | input(l); input(r);
| ^~~~~
curtains.cpp:12:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
12 | #define input(x) scanf("%lld", &x);
| ~~~~~^~~~~~~~~~~~
curtains.cpp:122:13: note: in expansion of macro 'input'
122 | input(l); input(r);
| ^~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |