#include <iostream>
#include <vector>
#include <algorithm>
#include <deque>
#include <set>
#include <utility>
#include <array>
using namespace std;
#define ALL(x) x.begin(), x.end()
using ll = long long;
#define N 200005
int n, q, t[N<<2], lz[N<<2];
pair<int, int> a[N];
void push(int v, int l, int r)
{
if (lz[v])
{
t[v] += lz[v];
if (l != r)
{
int m = (l+r)/2, vl=v+1, vr=v+(m-l+1)*2;
lz[vl]+=lz[v],lz[vr]+=lz[v];
}
lz[v] = 0;
}
}
void update(int v, int l, int r, int x, int y, int k)
{
push(v, l, r);
if (r < x || y < l) return;
if (x <= l && r <= y) { lz[v] += k; push(v, l, r); return; }
int m = (l+r)/2, vl=v+1, vr=v+(m-l+1)*2;
update(vl, l, m, x, y, k), update(vr, m+1, r, x, y, k);
t[v] = max(t[vl], t[vr]);
}
void update(int x, int y, int k) { update(0, 1, 2*n, x, y, k); }
int query(int v, int l, int r, int x, int y)
{
push(v, l, r);
if (r < x || y < l) return 0;
if (x <= l && r <= y) return t[v];
int m = (l+r)/2, vl=v+1, vr=v+(m-l+1)*2;
return max(query(vl, l, m, x, y), query(vr, m+1, r, x, y));
}
int query(int x, int y) { return query(0, 1, 2*n, x, y); }
void compress()
{
vector<int> C;
C.reserve(2*n);
for (int i = 0; i < n; ++i) C.push_back(a[i].first), C.push_back(a[i].second);
sort(ALL(C));
C.erase(unique(ALL(C)), C.end());
for (int i = 0; i < n; ++i) a[i].first = lower_bound(ALL(C), a[i].first) - C.begin() + 1,
a[i].second = lower_bound(ALL(C), a[i].second) - C.begin() + 1;
}
struct qry
{
int l, r, i;
bool operator<(const qry &o)
{
if (l/400 != o.l/400) return l<o.l;
if (r!=o.r) return r>o.r;
return i<o.i;
}
} b[N];
int ans[N];
int main()
{
cin.tie(nullptr)->sync_with_stdio(false);
cin >> n;
for (int i = 0; i < n; ++i) cin >> a[i].first >> a[i].second;
compress();
cin >> q;
for (int i = 0; i < q; ++i) cin >> b[i].l >> b[i].r, --b[i].l, --b[i].r, b[i].i = i;
sort(b, b+q);
int l = b[0].l, r = b[0].l-1;
for (int i = 0; i < q; ++i)
{
auto [L, R, j] = b[i];
while (l < L) update(a[l].first, a[l].second, -1), ++l;
while (r > R) update(a[r].first, a[r].second, -1), --r;
while (l > L) --l, update(a[l].first, a[l].second, 1);
while (r < R) ++r, update(a[r].first, a[r].second, 1);
ans[j] = query(1, 2*n);
}
for (int i = 0; i < q; ++i) cout << ans[i] << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
214 ms |
10964 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
264 ms |
6744 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
264 ms |
6744 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1008 ms |
11064 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
214 ms |
10964 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
