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>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
#define pii pair<int, int>
#define f first
#define s second
const int N = 100005;
int n, q, m;
ordered_set bit[N];
map<int, int> mp;
pii arr[N];
pair<pii, pii> queries[N];
int ans[N];
void upd(int x, int y){
for(; x<N; x = (x|(x+1)))
bit[x].insert(y);
}
int query(int x, int y){
int res = 0;
for(; x>=0; x = (x&(x+1))-1)
res += bit[x].order_of_key(y+1);
return res;
}
int main(){
// freopen("a.in", "r", stdin);
cin.tie(0)->sync_with_stdio(0);
cin >> n >> q;
vector<int> tmp;
for(int i = 0; i<n; ++i)
cin >> arr[i].f >> arr[i].s, tmp.push_back(arr[i].f);
sort(arr, arr+n, [&](pii a, pii b){return a.f+a.s<b.f+b.s;});
sort(tmp.begin(), tmp.end());
tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end());
m = tmp.size();
for(int i = 0; i<m; ++i)
mp[tmp[i]] = i;
for(int i = 0; i<q; ++i)
cin >> queries[i].s.f >> queries[i].s.s >> queries[i].f.f, queries[i].f.s = i;
sort(queries, queries+q);
for(int i = q-1, j = n-1; i>=0; --i){
while(j>=0 && arr[j].f+arr[j].s>=queries[i].f.f)
upd(m-1-mp[arr[j].f], 1e9-arr[j].s), --j;
int id = lower_bound(tmp.begin(), tmp.end(), queries[i].s.f)-tmp.begin();
ans[queries[i].f.s] = query(m-1-id, 1e9-queries[i].s.s);
}
for(int i = 0; i<q; ++i)
cout << ans[i] << '\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... |