#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define hash hashy
#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;
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){
}
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);
}
ii que[N];
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, 0)) - 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";
int itr = 0;
for(set<ii>::iterator it = se.begin(); it != se.end(); it++){
itr++;
que[itr] = (*it);
}
//stack<ii> que;
//for(set<ii>::iterator it = se.begin(); it != se.end(); it++) 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(1, 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(!itr) break;
ii temp = que[itr];
//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[students2[j].se].se], -1);
int pos = uomp[students1[temp.se].se];
for(; pos <= n + q; pos += pos & -pos) bit[pos]++;
//upd(uomp[students1[temp.se].se], 1);
itr--;
}
int temp = lower_bound(students2 + 1, students2 + n + 1, make_pair(queries[it].se, 0)) - 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);
int pos = uomp[students1[students2[j].se].se];
for(; pos <= n + q; pos += pos & -pos) bit[pos]--;
}
}
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);
int pos = uomp[students1[students2[j].se].se];
for(; pos <= n + q; pos += pos & -pos) bit[pos]++;
}
}
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);
int pos = uomp[students1[ind].se];
for(; pos <= n + q; pos += pos & -pos) bit[pos]++;
}
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:20:21: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
20 | const int oo = 1e18 + 7, mod = 1e9 + 7;
| ~~~~~^~~
examination.cpp: In function 'void process()':
examination.cpp:72:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
72 | for(int i = 0; i < vc.size(); i++) uomp[vc[i]] = i + 1;
| ~~^~~~~~~~~~~
examination.cpp: In function 'int main()':
examination.cpp:158:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
158 | freopen("exam.txt", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
