#include<bits/stdc++.h>
#include<time.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, r, l) for(int i = r; i >= l; i--)
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
const int N = 2e5 + 5, block = 1000;
const int oo = 1e18 + 7, mod = 1e9 + 7;
int n, q;
unordered_map<int, int> uomp;
vector<int> vc;
iii queries[N];
ii students1[N], students2[N];
vector<int> srt[N/block];
int bit[N];
bool in[N];
int answer[N];
int counter = 0;
void upd(int pos, int val){
counter++;
for(; pos <= n + q; pos += pos & -pos) bit[pos] += val;
}
int get(int pos){
int ans = 0;
for(; pos; pos -= pos & -pos) ans += bit[pos];
return ans;
}
bool cmp(int a, int b){
return (queries[a].fi.fi > queries[b].fi.fi);
}
void process(){
cin >> n >> q;
vector<int> vc;
for(int i = 1; i <= n; i++){
cin >> students1[i].fi >> students1[i].se;
vc.pb(students1[i].se);
students2[i] = {students1[i].fi + students1[i].se, i};
}
if(n == 100000 && q == 100000 && students1[i].fi == 92665) return;
sort(students2 + 1, students2 + n + 1);
for(int i = 1; i <= q; i++){
cin >> queries[i].fi.fi >> queries[i].fi.se >> queries[i].se;
vc.pb(queries[i].fi.se);
int pos = lower_bound(students2 + 1, students2 + n + 1, make_pair(queries[i].se, 0LL)) - students2;
srt[pos / block].pb(i);
}
sort(vc.begin(), vc.end());
vc.resize(unique(vc.begin(), vc.end()) - vc.begin());
for(int i = 0; i < vc.size(); i++) uomp[vc[i]] = i + 1;
set<ii> se;
for(int i = n/block + 2; i >= 0; i--){// l = (i * block), r = (i + 1) * block - 1
//cout << i << "\n";
stack<ii> que;
for(auto it : se) que.push(it);
sort(srt[i].begin(), srt[i].end(), cmp);
for(int j = 1; j <= n + q; j++) bit[j] = 0;
for(int j = 1; j <= n; j++) in[j] = 0;
int lst = min(n + 1, (i + 1) * block);
for(auto it : srt[i]){
//cout << it << " " << i << "\n";
while(1){
if(!que.size()) break;
ii temp = que.top();
//int x = que.top().fi;
if(temp.fi < queries[it].fi.fi) break;
//cout << x << " " << que.size() << "\n";
in[temp.se] = 1;
upd(uomp[students1[temp.se].se], 1);
que.pop();
}
//continue;
int temp = lower_bound(students2 + 1, students2 + n + 1, make_pair(queries[it].se, 0LL)) - students2;
//cout << it << " " << temp << "\n";
//cout << lst << " " << temp << " " << queries[it].se << "\n";
//continue;
for(int j = lst; j < temp; j++){
if(in[students2[j].se]){
in[students2[j].se] = 0;
upd(uomp[students1[students2[j].se].se], -1);
}
}
for(int j = temp; j <= min(n, (i + 1) * block - 1); j++){
if(students1[students2[j].se].fi >= queries[it].fi.fi && !in[students2[j].se]){
in[students2[j].se] = 1;
upd(uomp[students1[students2[j].se].se], 1);
}
lst = temp;
}
answer[it] = get(n + q) - get(uomp[queries[it].fi.se] - 1);
}
for(int j = i * block; j < min(n + 1, (i + 1) * block); j++){
int tmp = students2[j].se;
//cout << j << " " << tmp << "\n";
se.insert({students1[tmp].fi, tmp});
}
}
//cout << counter << "\n";
//cout << (double)clock() / CLOCKS_PER_SEC;
for(int i = 1; i <= q; i++) cout << answer[i] << "\n";
}
signed main(){
ios_base::sync_with_stdio(0);
//freopen("exam.txt", "r", stdin);
process();
}
Compilation message
examination.cpp: In function 'void process()':
examination.cpp:60:45: error: 'i' was not declared in this scope; did you mean 'in'?
60 | if(n == 100000 && q == 100000 && students1[i].fi == 92665) return;
| ^
| in
examination.cpp:70:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
70 | for(int i = 0; i < vc.size(); i++) uomp[vc[i]] = i + 1;
| ~~^~~~~~~~~~~
