// from duckindog wth depression
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
struct Q{
int p = 0, q = 0, i = 0;
} que[N];
int n;
int l[N], r[N];
int m;
int f[4 * N], lazy[4 * N];
void push(int s, int l, int r) {
if (!lazy[s]) return;
int mid = l + r >> 1;
int lt = mid - l + 1, rt = r - mid;
f[s * 2] += lt * lazy[s]; f[s * 2 + 1] += rt * lazy[s];
lazy[s * 2] += lazy[s]; lazy[s * 2 + 1] += lazy[s];
lazy[s] = 0;
}
void update(int s, int l, int r, int u, int v, int x) {
if (v < l || u > r) return;
if (u <= l && r <= v) {
f[s] += (r - l + 1) * x;
lazy[s] += x;
return;
}
push(s, l, r);
int mid = l + r >> 1;
update(s * 2, l, mid, u, v, x); update(s * 2 + 1, mid + 1, r, u, v, x);
f[s] = max(f[s * 2], f[s * 2 + 1]);
}
int query(int s, int l, int r, int u, int v) {
if (v < l || u > r) return 0;
if (u <= l && r <= v) return f[s];
push(s, l, r);
int mid = l + r >> 1;
return max(query(s * 2, l, mid, u, v), query(s * 2 + 1, mid + 1, r, u, v));
}
int32_t main() {
cin.tie(0)->sync_with_stdio(0);
if (fopen("duck.inp", "r")) {
freopen("duck.inp", "r", stdin);
freopen("duck.out", "w", stdout);
}
cin >> n;
vector<int> rrh;
map<int, int> rvs;
for (int i = 1; i <= n; ++i) {
cin >> l[i] >> r[i];
rrh.push_back(l[i]);
rrh.push_back(r[i]);
}
//rrh
sort(rrh.begin(), rrh.end());
rrh.resize(unique(rrh.begin(), rrh.end()) - rrh.begin());
int sz = rrh.size();
for (int i = 0; i < sz; ++i) rvs[rrh[i]] = i + 1;
//end rrh
cin >> m;
for (int i = 1; i <= n; ++i) {
int p, q; cin >> p >> q;
que[i] = {p, q, i};
}
sort(que + 1, que + m + 1, [&] (Q a, Q b){
if (a.p == b.p) return a.q < b.q;
return a.p < b.p;
});
int lt = 0, rt = 0;
for (int i = 1; i <= m; ++i) {
memset(f, 0, sizeof f);
memset(lazy, 0, sizeof lazy);
int p = que[i].p, q = que[i].q;
for (int j = p; j <= q; ++j) update(1, 1, sz, l[j], r[j], 1);
cout << f[1] << '\n';
}
}
Compilation message
Main.cpp: In function 'void push(int, int, int)':
Main.cpp:19:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
19 | int mid = l + r >> 1;
| ~~^~~
Main.cpp: In function 'void update(int, int, int, int, int, int)':
Main.cpp:35:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
35 | int mid = l + r >> 1;
| ~~^~~
Main.cpp: In function 'int query(int, int, int, int, int)':
Main.cpp:43:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
43 | int mid = l + r >> 1;
| ~~^~~
Main.cpp: In function 'int32_t main()':
Main.cpp:82:7: warning: unused variable 'lt' [-Wunused-variable]
82 | int lt = 0, rt = 0;
| ^~
Main.cpp:82:15: warning: unused variable 'rt' [-Wunused-variable]
82 | int lt = 0, rt = 0;
| ^~
Main.cpp:51:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
51 | freopen("duck.inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:52:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
52 | freopen("duck.out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
120 ms |
33624 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
452 ms |
9464 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
452 ms |
9464 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
157 ms |
34712 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
120 ms |
33624 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
