#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5 + 2;
// int num_node = 0;
int n , q , m;
pair < ll , ll > a[N + 2];
vector < ll > vt;
bool cmp_1(pair < int , int > g , pair < int , int > h){
return g.first < h.first;
}
bool cmp_2(pair < int , int > g , pair < int , int > h){
return g.first < h.first;
}
struct per{
vector <pair < int , int > > bit[N + 2];
void update(int id , int timer){
while(id <= m){
if(bit[id].empty())bit[id].push_back({timer , 1});
else{
int cur = bit[id].back().second;
bit[id].push_back({timer , cur + 1});
}
id += id &(-id);
}
}
int get(int id , int timer){
int ans = 0;
while(id > 0){
if(bit[id].size()){
int k = upper_bound(bit[id].begin() , bit[id].end() , make_pair(timer , 0), cmp_1) - bit[id].begin();
k--;
if(k >= 0){
ans += bit[id][k].second;
}
}
id -= id &(-id);
}
return ans;
}
}BIT_ONE ,BIT_TWO;
int get_one(ll l , int timer_l , int timer_r){
int k = upper_bound(vt.begin() , vt.end() , l) - vt.begin();
if(k == 0)return 0;
return BIT_ONE.get(m , timer_r) - BIT_ONE.get(k - 1 , timer_r) + BIT_ONE.get(k - 1 , timer_l - 1) - BIT_ONE.get(m , timer_l - 1);
}
int get_two(ll c , int timer_l , int timer_r){
int k = upper_bound(vt.begin() , vt.end() , c) - vt.begin();
if(k == 0)return 0;
return BIT_TWO.get(m , timer_r) - BIT_TWO.get(k - 1 , timer_r) + BIT_TWO.get(k - 1 , timer_l - 1) - BIT_TWO.get(m , timer_l - 1);
}
struct qq{
ll t , c;
int id;
};
vector < qq > query[N + 2];
int ans[N + 2];
void pre(){
for(int i= 1; i <= n ; i ++){
vt.push_back(a[i].second);
vt.push_back(a[i].first + a[i].second);
}
sort(vt.begin() , vt.end());
vt.erase(unique(vt.begin() , vt.end()) , vt.end());
m= vt.size();
for(int i = 1 ; i <= n; i ++){
int k = upper_bound(vt.begin() , vt.end() , a[i].second) - vt.begin();
BIT_ONE.update(k , i);
k = upper_bound(vt.begin() , vt.end() , a[i].first + a[i].second)- vt.begin();
BIT_TWO.update(k , i);
// cout << get_two(100 , 1 , n) << ' ';
}
// for(auto v: vt)cout <<v << ' ';
// cout << BIT_ONE.get(m , n) -BIT_ONE.get(k - 1 , n) << '\n';
// cout <<'\n';
}
int bin(ll t , ll c , int i){
int l = i;
int r = n ;
while(l <= r){
int mid = (l + r) / 2;
if(c - a[mid].first >= t){
l = mid + 1;
}
else r = mid - 1;
}
return l - 1;
}
void solve() {
cin >> n >> q;
for(int i = 1; i <= n ; i ++){
cin >> a[i].first >> a[i].second;
}
sort(a + 1 , a + n + 1);
for(int i = 1 ; i <= q ; i ++){
ll s , t , c;
cin >> s >> t >> c;
int k = lower_bound(a + 1 , a + n + 1, make_pair(s , 0), cmp_2) - a;
query[k].push_back({t , c , i});
vt.push_back(t);
vt.push_back(c);
}
pre();
for(int i =n ;i >= 1; i --){
for(auto cur : query[i]){
int kl = bin(cur.t , cur.c , i);
if(kl >= i){
ans[cur.id] += get_two(cur.c , i , kl);
}
if(kl < n){
ans[cur.id] += get_one(cur.t , kl + 1 , n);
}
}
}
for(int i = 1 ; i <= q; i ++){
cout << ans[i] << '\n';
}
}
signed main() {
ios::sync_with_stdio(0), cin.tie(0);
#define _ "joi1."
if (fopen(_ "inp", "r")) {
freopen(_ "inp", "r", stdin);
freopen(_ "out", "w", stdout);
}
solve();
}
Compilation message
examination.cpp: In function 'int main()':
examination.cpp:129:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
129 | freopen(_ "inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
examination.cpp:130:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
130 | freopen(_ "out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
7512 KB |
Output is correct |
| 2 |
Correct |
3 ms |
7516 KB |
Output is correct |
| 3 |
Correct |
4 ms |
7388 KB |
Output is correct |
| 4 |
Correct |
3 ms |
7512 KB |
Output is correct |
| 5 |
Correct |
3 ms |
7516 KB |
Output is correct |
| 6 |
Correct |
3 ms |
7512 KB |
Output is correct |
| 7 |
Correct |
10 ms |
8556 KB |
Output is correct |
| 8 |
Correct |
10 ms |
8540 KB |
Output is correct |
| 9 |
Correct |
10 ms |
8536 KB |
Output is correct |
| 10 |
Correct |
8 ms |
8504 KB |
Output is correct |
| 11 |
Correct |
9 ms |
8540 KB |
Output is correct |
| 12 |
Correct |
6 ms |
8028 KB |
Output is correct |
| 13 |
Correct |
9 ms |
8284 KB |
Output is correct |
| 14 |
Correct |
9 ms |
8296 KB |
Output is correct |
| 15 |
Correct |
10 ms |
8340 KB |
Output is correct |
| 16 |
Correct |
6 ms |
8284 KB |
Output is correct |
| 17 |
Correct |
8 ms |
8476 KB |
Output is correct |
| 18 |
Correct |
4 ms |
8028 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
173 ms |
74680 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
173 ms |
74680 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
7512 KB |
Output is correct |
| 2 |
Correct |
3 ms |
7516 KB |
Output is correct |
| 3 |
Correct |
4 ms |
7388 KB |
Output is correct |
| 4 |
Correct |
3 ms |
7512 KB |
Output is correct |
| 5 |
Correct |
3 ms |
7516 KB |
Output is correct |
| 6 |
Correct |
3 ms |
7512 KB |
Output is correct |
| 7 |
Correct |
10 ms |
8556 KB |
Output is correct |
| 8 |
Correct |
10 ms |
8540 KB |
Output is correct |
| 9 |
Correct |
10 ms |
8536 KB |
Output is correct |
| 10 |
Correct |
8 ms |
8504 KB |
Output is correct |
| 11 |
Correct |
9 ms |
8540 KB |
Output is correct |
| 12 |
Correct |
6 ms |
8028 KB |
Output is correct |
| 13 |
Correct |
9 ms |
8284 KB |
Output is correct |
| 14 |
Correct |
9 ms |
8296 KB |
Output is correct |
| 15 |
Correct |
10 ms |
8340 KB |
Output is correct |
| 16 |
Correct |
6 ms |
8284 KB |
Output is correct |
| 17 |
Correct |
8 ms |
8476 KB |
Output is correct |
| 18 |
Correct |
4 ms |
8028 KB |
Output is correct |
| 19 |
Runtime error |
173 ms |
74680 KB |
Execution killed with signal 11 |
| 20 |
Halted |
0 ms |
0 KB |
- |
