#include<bits/stdc++.h>
//#define int long long
#define pii pair<ll,ll>
#define fi first
#define se second
using namespace std;
using ll = long long;
using ldb = long double;
const int N = (int)1e8;
const int maxN = (int)2e5 + 5;
const int mod = 1e9 + 7;
const ll infty = 1e18;
void InputFile()
{
//freopen("scrivener.inp","r",stdin);
//freopen("scrivener.out","w",stdout);
freopen("test.out","r",stdin);
}
void FastInput()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
}
int n,q;
int s[maxN],t[maxN];
int id[maxN];
vector<int> vec;
bool FA(int i,int j)
{
return s[i] < s[j];
}
vector<int> ST[2][4*maxN];
vector<int> Merge(vector<int> a,vector<int> b)
{
vector<int> res;
int pta = 0;
int ptb = 0;
while(pta < a.size() || ptb < b.size())
{
if(pta == a.size())
{
res.push_back(b[ptb]);
ptb++;
}
else if(ptb == b.size())
{
res.push_back(a[pta]);
pta++;
}
else if(a[pta] <= b[ptb])
{
res.push_back(a[pta]);
pta++;
}
else
{
res.push_back(b[ptb]);
ptb++;
}
}
return res;
}
void Build(int id,int l,int r)
{
if(l == r)
{
ST[0][id] = {t[l]};
ST[1][id] = {s[l] + t[l]};
return;
}
int mid = (l + r) / 2;
Build(id * 2,l,mid);
Build(id * 2 + 1,mid + 1,r);
ST[0][id] = Merge(ST[0][id*2],ST[0][id*2+1]);
ST[1][id] = Merge(ST[1][id*2],ST[1][id*2+1]);
}
int Get(int id,int l,int r,int u,int v,int cval,int t)
{
if(v < l || u > r) return 0;
if(u <= l && r <= v)
{
int val = ST[t][id].size() - (lower_bound(ST[t][id].begin(),ST[t][id].end(),cval) - ST[t][id].begin());
return val;
}
int mid = (l + r) / 2;
return Get(id * 2,l,mid,u,v,cval,t) + Get(id * 2 + 1,mid + 1,r,u,v,cval,t);
}
void Read()
{
cin >> n >> q;
for(int i = 1;i <= n;i++)
{
cin >> s[i] >> t[i];
id[i] = i;
}
sort(id + 1,id + n + 1,FA);
for(int i = 1;i <= n;i++) vec.push_back(s[id[i]]);
for(int i = 1;i <= n;i++) s[i] = vec[i-1];
vec.clear();
for(int i = 1;i <= n;i++) vec.push_back(t[id[i]]);
for(int i = 1;i <= n;i++) t[i] = vec[i-1];
Build(1,1,n);
/*for(int i = 1;i <= n;i++)
{
cout << s[i] <<' '<< t[i] <<'\n';
}*/
while(q--)
{
int A,B,C;
cin >> A >> B >> C;
int L = lower_bound(s + 1,s + n + 1,A) - s;
int R = upper_bound(s + 1,s + n + 1,C - B) - s;
int res = 0;
if(L <= R - 1)
{
res += Get(1,1,n,L,R-1,C,1);
}
R = max(R,L);
res += (Get(1,1,n,R,n,B,0));
cout << res <<'\n';
}
}
void Solve()
{
}
void Debug()
{
//Main_sub();
//Naive();
}
int32_t main()
{
FastInput();
//InputFile();
//int sub_type;
//cin >> sub_type;
//Sieve();
int test;
//cin >> test;
test = 1;
while(test--)
//for(int prc = 1; prc <= test; prc++)
{
Read();
Solve();
//Debug();
}
}
/*
4 1
1 1 1 1
1 2
2 3
3 4
*/
Compilation message
examination.cpp: In function 'std::vector<int> Merge(std::vector<int>, std::vector<int>)':
examination.cpp:45:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
45 | while(pta < a.size() || ptb < b.size())
| ~~~~^~~~~~~~~~
examination.cpp:45:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
45 | while(pta < a.size() || ptb < b.size())
| ~~~~^~~~~~~~~~
examination.cpp:47:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
47 | if(pta == a.size())
| ~~~~^~~~~~~~~~~
examination.cpp:52:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
52 | else if(ptb == b.size())
| ~~~~^~~~~~~~~~~
examination.cpp: In function 'void InputFile()':
examination.cpp:19:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
19 | freopen("test.out","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
18 ms |
37844 KB |
Output is correct |
2 |
Correct |
19 ms |
37844 KB |
Output is correct |
3 |
Correct |
19 ms |
37856 KB |
Output is correct |
4 |
Correct |
22 ms |
37864 KB |
Output is correct |
5 |
Correct |
19 ms |
37904 KB |
Output is correct |
6 |
Correct |
19 ms |
37812 KB |
Output is correct |
7 |
Correct |
26 ms |
38776 KB |
Output is correct |
8 |
Correct |
25 ms |
38740 KB |
Output is correct |
9 |
Correct |
25 ms |
38740 KB |
Output is correct |
10 |
Correct |
25 ms |
38740 KB |
Output is correct |
11 |
Correct |
26 ms |
38684 KB |
Output is correct |
12 |
Correct |
23 ms |
38604 KB |
Output is correct |
13 |
Correct |
25 ms |
38748 KB |
Output is correct |
14 |
Correct |
25 ms |
38728 KB |
Output is correct |
15 |
Correct |
24 ms |
38740 KB |
Output is correct |
16 |
Correct |
22 ms |
38692 KB |
Output is correct |
17 |
Correct |
24 ms |
38752 KB |
Output is correct |
18 |
Correct |
22 ms |
38612 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
291 ms |
66644 KB |
Output is correct |
2 |
Correct |
296 ms |
69060 KB |
Output is correct |
3 |
Correct |
290 ms |
69156 KB |
Output is correct |
4 |
Correct |
274 ms |
68364 KB |
Output is correct |
5 |
Correct |
222 ms |
68308 KB |
Output is correct |
6 |
Correct |
217 ms |
67576 KB |
Output is correct |
7 |
Correct |
276 ms |
69132 KB |
Output is correct |
8 |
Correct |
287 ms |
69064 KB |
Output is correct |
9 |
Correct |
255 ms |
68940 KB |
Output is correct |
10 |
Correct |
178 ms |
68112 KB |
Output is correct |
11 |
Correct |
240 ms |
68136 KB |
Output is correct |
12 |
Correct |
158 ms |
67304 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
291 ms |
66644 KB |
Output is correct |
2 |
Correct |
296 ms |
69060 KB |
Output is correct |
3 |
Correct |
290 ms |
69156 KB |
Output is correct |
4 |
Correct |
274 ms |
68364 KB |
Output is correct |
5 |
Correct |
222 ms |
68308 KB |
Output is correct |
6 |
Correct |
217 ms |
67576 KB |
Output is correct |
7 |
Correct |
276 ms |
69132 KB |
Output is correct |
8 |
Correct |
287 ms |
69064 KB |
Output is correct |
9 |
Correct |
255 ms |
68940 KB |
Output is correct |
10 |
Correct |
178 ms |
68112 KB |
Output is correct |
11 |
Correct |
240 ms |
68136 KB |
Output is correct |
12 |
Correct |
158 ms |
67304 KB |
Output is correct |
13 |
Correct |
356 ms |
69528 KB |
Output is correct |
14 |
Correct |
350 ms |
69560 KB |
Output is correct |
15 |
Correct |
314 ms |
69096 KB |
Output is correct |
16 |
Correct |
351 ms |
68784 KB |
Output is correct |
17 |
Correct |
232 ms |
68720 KB |
Output is correct |
18 |
Correct |
217 ms |
67576 KB |
Output is correct |
19 |
Correct |
372 ms |
69500 KB |
Output is correct |
20 |
Correct |
381 ms |
69504 KB |
Output is correct |
21 |
Correct |
372 ms |
69576 KB |
Output is correct |
22 |
Correct |
210 ms |
68236 KB |
Output is correct |
23 |
Correct |
230 ms |
68128 KB |
Output is correct |
24 |
Correct |
158 ms |
67240 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
18 ms |
37844 KB |
Output is correct |
2 |
Correct |
19 ms |
37844 KB |
Output is correct |
3 |
Correct |
19 ms |
37856 KB |
Output is correct |
4 |
Correct |
22 ms |
37864 KB |
Output is correct |
5 |
Correct |
19 ms |
37904 KB |
Output is correct |
6 |
Correct |
19 ms |
37812 KB |
Output is correct |
7 |
Correct |
26 ms |
38776 KB |
Output is correct |
8 |
Correct |
25 ms |
38740 KB |
Output is correct |
9 |
Correct |
25 ms |
38740 KB |
Output is correct |
10 |
Correct |
25 ms |
38740 KB |
Output is correct |
11 |
Correct |
26 ms |
38684 KB |
Output is correct |
12 |
Correct |
23 ms |
38604 KB |
Output is correct |
13 |
Correct |
25 ms |
38748 KB |
Output is correct |
14 |
Correct |
25 ms |
38728 KB |
Output is correct |
15 |
Correct |
24 ms |
38740 KB |
Output is correct |
16 |
Correct |
22 ms |
38692 KB |
Output is correct |
17 |
Correct |
24 ms |
38752 KB |
Output is correct |
18 |
Correct |
22 ms |
38612 KB |
Output is correct |
19 |
Correct |
291 ms |
66644 KB |
Output is correct |
20 |
Correct |
296 ms |
69060 KB |
Output is correct |
21 |
Correct |
290 ms |
69156 KB |
Output is correct |
22 |
Correct |
274 ms |
68364 KB |
Output is correct |
23 |
Correct |
222 ms |
68308 KB |
Output is correct |
24 |
Correct |
217 ms |
67576 KB |
Output is correct |
25 |
Correct |
276 ms |
69132 KB |
Output is correct |
26 |
Correct |
287 ms |
69064 KB |
Output is correct |
27 |
Correct |
255 ms |
68940 KB |
Output is correct |
28 |
Correct |
178 ms |
68112 KB |
Output is correct |
29 |
Correct |
240 ms |
68136 KB |
Output is correct |
30 |
Correct |
158 ms |
67304 KB |
Output is correct |
31 |
Correct |
356 ms |
69528 KB |
Output is correct |
32 |
Correct |
350 ms |
69560 KB |
Output is correct |
33 |
Correct |
314 ms |
69096 KB |
Output is correct |
34 |
Correct |
351 ms |
68784 KB |
Output is correct |
35 |
Correct |
232 ms |
68720 KB |
Output is correct |
36 |
Correct |
217 ms |
67576 KB |
Output is correct |
37 |
Correct |
372 ms |
69500 KB |
Output is correct |
38 |
Correct |
381 ms |
69504 KB |
Output is correct |
39 |
Correct |
372 ms |
69576 KB |
Output is correct |
40 |
Correct |
210 ms |
68236 KB |
Output is correct |
41 |
Correct |
230 ms |
68128 KB |
Output is correct |
42 |
Correct |
158 ms |
67240 KB |
Output is correct |
43 |
Correct |
377 ms |
71472 KB |
Output is correct |
44 |
Correct |
374 ms |
71488 KB |
Output is correct |
45 |
Correct |
352 ms |
71448 KB |
Output is correct |
46 |
Correct |
369 ms |
69856 KB |
Output is correct |
47 |
Correct |
244 ms |
69960 KB |
Output is correct |
48 |
Correct |
204 ms |
67492 KB |
Output is correct |
49 |
Correct |
420 ms |
71404 KB |
Output is correct |
50 |
Correct |
384 ms |
71428 KB |
Output is correct |
51 |
Correct |
462 ms |
71244 KB |
Output is correct |
52 |
Correct |
190 ms |
69696 KB |
Output is correct |
53 |
Correct |
232 ms |
68992 KB |
Output is correct |