#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
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 = 900;
const int oo = 1e18 + 7, mod = 1e9 + 7;
struct hash {
static uint64_t splitmix64(uint64_t x) {
// http://xorshift.di.unimi.it/splitmix64.c
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
int n, q;
gp_hash_table<int, int, hash> 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);
vector<ii> vc1;
for(int j = max(1LL, i * block); j < min(n + 1, (i + 1) * block); j++){
int tmp = students2[j].se;
//if(!tmp) cout << j << " " << tmp << "\n";
vc1.pb({students1[tmp].fi, tmp});
}
sort(vc1.begin(), vc1.end());
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();
}
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 < lst; 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;
while(1){
if(!vc1.size()) break;
if(vc1.back().fi < queries[it].fi.fi) break;
int ind = vc1.back().se;
if(!in[ind] && students1[ind].fi + students1[ind].se >= queries[it].se){
in[ind] = 1;
//assert(ind);
upd(uomp[students1[ind].se], 1);
}
vc1.pop_back();
//cout << vc1.size() << "\n";
}
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:40:29: error: template argument 3 is invalid
40 | gp_hash_table<int, int, hash> uomp;
| ^
examination.cpp: In function 'void process()':
examination.cpp:87: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]
87 | for(int i = 0; i < vc.size(); i++) uomp[vc[i]] = i + 1;
| ~~^~~~~~~~~~~
examination.cpp:87:41: error: invalid types 'int[__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type {aka long long int}]' for array subscript
87 | for(int i = 0; i < vc.size(); i++) uomp[vc[i]] = i + 1;
| ^
examination.cpp:113:14: error: invalid types 'int[long long int]' for array subscript
113 | upd(uomp[students1[temp.se].se], 1);
| ^
examination.cpp:123:14: error: invalid types 'int[long long int]' for array subscript
123 | upd(uomp[students1[students2[j].se].se], -1);
| ^
examination.cpp:129:14: error: invalid types 'int[long long int]' for array subscript
129 | upd(uomp[students1[students2[j].se].se], 1);
| ^
examination.cpp:140:14: error: invalid types 'int[long long int]' for array subscript
140 | upd(uomp[students1[ind].se], 1);
| ^
examination.cpp:145:38: error: invalid types 'int[long long int]' for array subscript
145 | answer[it] = get(n + q) - get(uomp[queries[it].fi.se] - 1);
| ^
examination.cpp: In function 'int main()':
examination.cpp:160:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
160 | freopen("exam.txt", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
