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>
using namespace std;
#define int long long
int n, d = 0, q, x[100005], y[100005], z[100005], cnt[200005];
bool mark[500005], Q[500005];
set<int> s;
struct NODE {
int x, y, z, idx;
bool operator < (NODE b) {
if(x != b.x) return x < b.x;
else return idx > b.idx;
}
} node[500005];
int bit[500005];
void update(int pos, int val) {
while(pos <= d) {
bit[pos] += val;
pos += pos & -pos;
}
}
int get(int pos) {
int res = 0;
while(pos > 0) {
res += bit[pos];
pos -= pos & -pos;
}
return res;
}
int range(int l, int r) {
return get(r) - get(l-1);
}
void cdq(int l, int r) {
int mid = (l + r) / 2;
if(l == r) return;
cdq(l, mid);
cdq(mid + 1, r);
for (int i = mid + 1; i <= r; i++) {
if(!Q[node[i].idx]) update(node[i].z, 1);
}
vector<NODE> v;
int p1;
p1 = mid+1;
for (int i = l; i <= mid; i++) {
while(p1 <= r && node[p1].y < node[i].y) {
v.push_back(node[p1]);
if(!Q[node[p1].idx]) update(node[p1].z, -1);
p1++;
}
v.push_back(node[i]);
cnt[node[i].idx] += range(node[i].z, d);
}
while(p1 <= r) {
v.push_back(node[p1]);
if(!Q[node[p1].idx]) update(node[p1].z, -1);
p1++;
}
for (int i = l; i <= r; i++) {
node[i] = v[i-l];
}
return;
}
map<int, int> mp;
signed main() {
cin >> n >> q;
for (int i = 1; i <= n; i++) {
cin >> node[i].x >> node[i].y;
node[i].z = node[i].x + node[i].y;
s.insert(node[i].x);
s.insert(node[i].y);
s.insert(node[i].z);
node[i].idx = i;
}
for (int i = 1; i <= q; i++) {
cin >> x[i] >> y[i] >> z[i];
s.insert(x[i]);
s.insert(y[i]);
s.insert(z[i]);
}
for (int i: s) mp[i] = ++d;
for (int i = 1; i <= n; i++) {
node[i].x = mp[node[i].x];
node[i].y = mp[node[i].y];
node[i].z = mp[node[i].z];
//cout << node[i].x << ' ' << node[i].y << ' ' << node[i].z << '\n';
}
for (int i = 1; i <= q; i++) {
x[i] = mp[x[i]];
y[i] = mp[y[i]];
z[i] = mp[z[i]];
node[i+n] = {x[i], y[i], z[i], i + n};
Q[i+n] = true;
}
sort(node + 1, node + 1 + q + n);
cdq(1, n+q);
for (int i = 1; i <= q; i++) {
cout << cnt[i+n] << '\n';
}
}
# | 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... |