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>
#define forr(_a,_b,_c) for(_a = (_b); _a <= (_c); ++_a)
#define ford(_a,_b,_c) for(_a = (_b) + 1; _a --> (_c);)
#define forf(_a,_b,_c) for(_a = (_b); _a < (_c); ++_a)
#define st first
#define nd second
#define ll long long
#define ull unsigned long long
#define pii pair <int,int>
#define pll pair <ll,ll>
#define piii pair <int,pii>
#define vi vector <int>
#define pb push_back
#define mp make_pair
#define all(x) begin(x),end(x)
#define file "test"
using namespace std;
const int N = 5e5 + 5;
const ll oo = 1e9;
const ll mod = 1e9 + 7;
const int uwu = 317;
pair <pii, pii> w[N];
int bit[uwu + 5][uwu + 5], n, q, i, j, k, ans[N], flag[N];
pii a[N];
vector <pii> f;
vi v[N];
void update (int id, int x){
for (; x > 0; x -= x & -x)
bit[id][x]++;
}
int get (int id, int x){
int res = 0;
for (; x <= uwu + 1; x += x & -x)
res += bit[id][x];
return res;
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef hqm
freopen(file".inp", "r", stdin); freopen(file".out", "w", stdout);
#endif
cin >> n >> q;
forr (i, 1, n)
cin >> a[i].st >> a[i].nd;
sort(a + 1, a + 1+ n);
forr (i, 1, n)
f.pb({a[i].st + a[i].nd, i});
forr (i, 1, n)
v[i / uwu].pb(a[i].nd);
forr (i, 0, n / uwu){
sort(all(v[i])), v[i].erase(unique(all(v[i])), v[i].end());
}
forr (i, 1, q)
cin >> w[i].nd.st >> w[i].nd.nd >> w[i].st.st, w[i].st.nd = i;
sort(w + 1, w + 1 + n, greater<pair<pii, pii>>());
sort(all(f));
int it = f.size() - 1;
forr (i, 1, q){
int z = w[i].st.st, x = w[i].nd.st, y = w[i].nd.nd, pos = w[i].st.nd;
while (it >= 0 && f[it].st >= z){
int id = f[it].nd / uwu;
flag[f[it].nd] = 1;
int tmp = lower_bound(all(v[id]), a[f[it].nd].nd) - v[id].begin() + 1;
//cout << f[it].st << " " << a[f[it].nd].st << " " << a[f[it].nd].nd << " " << id << " " << tmp << "\n";
update(id, tmp);
it--;
}
int j = n / uwu;
while (j >= 0 && a[uwu * j].st >= x){
int e = lower_bound(all(v[j]), y) - v[j].begin() + 1;
// cout << e << "\n";
ans[pos] += get(j, e);
j--;
}
if (j >= 0)
ford (k, uwu * (j + 1) - 1, j * uwu){
ans[pos] += (y <= a[k].nd && x <= a[k].st) * flag[k];
}
// cout << y << "\n";
}
forr (i, 1, q)
cout << ans[i] << "\n";
return 0;
}
/*
*/
# | 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... |