#include<bits/stdc++.h>
#define mod 1000000007
#define inf 1e17
using namespace std;
struct aint {
vector<long long> a;
vector<long long> lazy;
void prop(long long node, long long left, long long right) {
a[node] += lazy[node];
if (left != right) {
lazy[2 * node] += lazy[node];
lazy[2 * node + 1] += lazy[2 * node + 1], lazy[node];
}
lazy[node] = 0;
}
void build(vector<long long>& b, long long node, long long left, long long right) {
if ((long long)a.size() == 0) {
long long n = b.size() - 1;
a = vector<long long>(4 * n);
lazy = vector<long long>(4 * n);
}
if (left == right) {
a[node] = b[left];
}
else {
long long mid = (left + right) / 2;
build(b, 2 * node, left, mid);
build(b, 2 * node + 1, mid + 1, right);
a[node] = min(a[2 * node], a[2 * node + 1]);
}
}
long long query(long long node, long long left, long long right, long long st, long long dr) {
if (left > right) {
return 2 * inf;
}
prop(node, left, right);
if (st <= left && dr >= right) {
return a[node];
}
if ((st<left || st>right) && (dr<left || dr>right)) {
return 2 * inf;
}
long long mid = (left + right) / 2;
return min(query(2 * node, left, mid, st, dr), query(2 * node + 1, mid + 1, right, st, dr));
}
void update(long long node, long long left, long long right, long long st, long long dr, long long val) {
if (left > right) {
return;
}
prop(node, left, right);
if (st <= left && dr >= right) {
lazy[node] += val;
return;
}
if ((st<left || st>right) && (dr<left || dr>right)) {
return;
}
long long mid = (left + right) / 2;
update(2 * node, left, mid, st, dr, val);
update(2 * node + 1, mid + 1, right, st, dr, val);
prop(2 * node, left, mid);
prop(2 * node + 1, mid + 1, right);
a[node] = min(a[2 * node], a[2 * node + 1]);
}
};
vector<pair<long long, long long>> a;
map<pair<long long, long long>, long long> poz;
long long n, q;
aint tree;
void add(long long ind) {
long long wh = poz[a[ind]];
tree.update(1, 1, n, wh, wh, -inf + a[ind].first);
tree.update(1, 1, n, wh, n, -a[ind].second);
}
void rem(long long ind) {
long long wh = poz[a[ind]];
tree.update(1, 1, n, wh, wh, inf);
tree.update(1, 1, n, wh, n, a[ind].second);
}
int main() {
std::ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> q;
a = vector<pair<long long, long long>>(n + 1);
vector<pair<long long, long long>> norm(n + 1);
for (long long i = 1; i <= n; ++i) {
cin >> a[i].second >> a[i].first;
norm[i] = a[i];
}
sort(norm.begin() + 1, norm.end());
for (long long i = 1; i <= n; ++i) {
poz[norm[i]] = i;
}
vector<long long> values(n + 1);
for (long long i = 1; i <= n; ++i) {
values[i] = inf;
}
tree.build(values, 1, 1, n);
long long p = 0;
vector<long long> right(n + 1);
for (long long i = 1; i <= n; ++i) {
if (i > 1) {
rem(i - 1);
}
if (p == i - 1) {
p++;
}
while (p <= n) {
add(p);
if (tree.query(1, 1, n, 1, n) <= 0) {
rem(p);
break;
}
p++;
}
right[i] = p - 1;
}
while (q--) {
long long st, dr;
cin >> st >> dr;
if (right[st] < dr) {
cout << 0 << '\n';
}
else {
cout << 1 << '\n';
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
