#include <bits/stdc++.h>
using namespace std;
#define getbit(x, i) ((x&(1<<(i))) != 0)
const int NM = 3e5, SZ = 550, LOG = 18;
struct node{
mutable int cnt, nxt[2];
node(int a, int b, int c){
cnt = a, nxt[0] = b, nxt[1] = c;
}
};
struct trie{
vector <node> T;
void add_node(){
T.push_back(node(0, -1, -1));
}
void init(){
T.clear();
add_node();
}
void add_int(int x){
int cur = 0;
for (int i = LOG; i >= 0; i--){
T[cur].cnt++;
int k = getbit(x, i);
if (T[cur].nxt[k] == -1){
add_node();
T[cur].nxt[k] = T.size()-1;
}
cur = T[cur].nxt[k];
}
T[cur].cnt++;
}
int get(int x){
int cur = 0, res = 0;
for (int i = LOG; i >= 0; i--){
int k = getbit(x, i);
if (k == 0){
if (T[cur].nxt[1] != -1) res += T[T[cur].nxt[1]].cnt;
}
if (T[cur].nxt[k] == -1) return res;
cur = T[cur].nxt[k];
}
res += T[cur].cnt;
return res;
}
};
int N, Q;
int S[NM+5], T[NM+5], sum[NM+5], X[NM+5], Y[NM+5], Z[NM+5];
map <int, bool> mark;
vector <int> sorted_arr, id1, id2;
int ans[NM+5];
trie T1[NM+5], T2[SZ+5];
int get(int x){
if (sorted_arr.back() < x) return -1;
return lower_bound(sorted_arr.begin(), sorted_arr.end(), x)-sorted_arr.begin();
}
bool cmp1(int x, int y){
return S[x] > S[y];
}
bool cmp2(int x, int y){
return X[x] > X[y];
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> N >> Q;
for (int i = 1; i <= N; i++){
cin >> S[i] >> T[i];
if (!mark[S[i]]){
sorted_arr.push_back(S[i]);
mark[S[i]] = 1;
}
if (!mark[T[i]]){
sorted_arr.push_back(T[i]);
mark[T[i]] = 1;
}
sum[i] = S[i]+T[i];
if (!mark[sum[i]]){
sorted_arr.push_back(sum[i]);
mark[sum[i]] = 1;
}
id1.push_back(i);
}
sort(sorted_arr.begin(), sorted_arr.end());
for (int i = 1; i <= N; i++){
S[i] = lower_bound(sorted_arr.begin(), sorted_arr.end(), S[i])-sorted_arr.begin();
T[i] = lower_bound(sorted_arr.begin(), sorted_arr.end(), T[i])-sorted_arr.begin();
sum[i] = lower_bound(sorted_arr.begin(), sorted_arr.end(), sum[i])-sorted_arr.begin();
}
for (int i = 1; i <= Q; i++){
cin >> X[i] >> Y[i] >> Z[i];
X[i] = get(X[i]);
Y[i] = get(Y[i]);
Z[i] = get(Z[i]);
if (X[i] == -1 || Y[i] == -1 || Z[i] == -1){
ans[i] = 0;
}
else{
id2.push_back(i);
}
}
for (int i = 0; i < sorted_arr.size(); i++)
T1[i].init();
for (int i = 0; i < SZ; i++)
T2[i].init();
sort(id1.begin(), id1.end(), cmp1);
sort(id2.begin(), id2.end(), cmp2);
int jj = 0;
for (int ii = 0; ii < id2.size(); ii++){
int i = id2[ii];
while (jj < id1.size()){
int j = id1[jj];
if (S[j] < X[i]) break;
T1[T[j]].add_int(sum[j]);
T2[T[j]/SZ].add_int(sum[j]);
jj++;
}
ans[i] = 0;
int L = (Y[i]+SZ-1)/SZ;
for (int k = L; k < SZ; k++)
ans[i] += T2[k].get(Z[i]);
for (int k = Y[i]; k < min((int)sorted_arr.size(), L*SZ); k++)
ans[i] += T1[k].get(Z[i]);
}
for (int i = 1; i <= Q; i++) cout << ans[i] << '\n';
return 0;
}
Compilation message
examination.cpp: In function 'int main()':
examination.cpp:112:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
112 | for (int i = 0; i < sorted_arr.size(); i++)
| ~~^~~~~~~~~~~~~~~~~~~
examination.cpp:120:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
120 | for (int ii = 0; ii < id2.size(); ii++){
| ~~~^~~~~~~~~~~~
examination.cpp:122:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
122 | while (jj < id1.size()){
| ~~~^~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
14940 KB |
Output is correct |
2 |
Correct |
2 ms |
14944 KB |
Output is correct |
3 |
Correct |
2 ms |
14940 KB |
Output is correct |
4 |
Correct |
2 ms |
14940 KB |
Output is correct |
5 |
Correct |
2 ms |
14992 KB |
Output is correct |
6 |
Correct |
2 ms |
14940 KB |
Output is correct |
7 |
Correct |
19 ms |
17016 KB |
Output is correct |
8 |
Correct |
20 ms |
16984 KB |
Output is correct |
9 |
Correct |
20 ms |
17116 KB |
Output is correct |
10 |
Correct |
13 ms |
15960 KB |
Output is correct |
11 |
Correct |
18 ms |
16720 KB |
Output is correct |
12 |
Correct |
7 ms |
14940 KB |
Output is correct |
13 |
Correct |
16 ms |
17004 KB |
Output is correct |
14 |
Correct |
16 ms |
16984 KB |
Output is correct |
15 |
Correct |
16 ms |
17172 KB |
Output is correct |
16 |
Correct |
17 ms |
16476 KB |
Output is correct |
17 |
Correct |
9 ms |
15448 KB |
Output is correct |
18 |
Correct |
3 ms |
14940 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
692 ms |
72496 KB |
Output is correct |
2 |
Correct |
687 ms |
72192 KB |
Output is correct |
3 |
Correct |
662 ms |
72136 KB |
Output is correct |
4 |
Correct |
329 ms |
33340 KB |
Output is correct |
5 |
Correct |
670 ms |
49908 KB |
Output is correct |
6 |
Correct |
180 ms |
16412 KB |
Output is correct |
7 |
Correct |
901 ms |
72128 KB |
Output is correct |
8 |
Correct |
694 ms |
72044 KB |
Output is correct |
9 |
Correct |
882 ms |
72268 KB |
Output is correct |
10 |
Correct |
518 ms |
46532 KB |
Output is correct |
11 |
Correct |
254 ms |
24880 KB |
Output is correct |
12 |
Correct |
41 ms |
15572 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
692 ms |
72496 KB |
Output is correct |
2 |
Correct |
687 ms |
72192 KB |
Output is correct |
3 |
Correct |
662 ms |
72136 KB |
Output is correct |
4 |
Correct |
329 ms |
33340 KB |
Output is correct |
5 |
Correct |
670 ms |
49908 KB |
Output is correct |
6 |
Correct |
180 ms |
16412 KB |
Output is correct |
7 |
Correct |
901 ms |
72128 KB |
Output is correct |
8 |
Correct |
694 ms |
72044 KB |
Output is correct |
9 |
Correct |
882 ms |
72268 KB |
Output is correct |
10 |
Correct |
518 ms |
46532 KB |
Output is correct |
11 |
Correct |
254 ms |
24880 KB |
Output is correct |
12 |
Correct |
41 ms |
15572 KB |
Output is correct |
13 |
Correct |
1069 ms |
72084 KB |
Output is correct |
14 |
Correct |
841 ms |
72244 KB |
Output is correct |
15 |
Correct |
658 ms |
72368 KB |
Output is correct |
16 |
Correct |
384 ms |
34620 KB |
Output is correct |
17 |
Correct |
641 ms |
50020 KB |
Output is correct |
18 |
Correct |
149 ms |
16468 KB |
Output is correct |
19 |
Correct |
1036 ms |
72152 KB |
Output is correct |
20 |
Correct |
1004 ms |
72012 KB |
Output is correct |
21 |
Correct |
1506 ms |
72152 KB |
Output is correct |
22 |
Correct |
506 ms |
46532 KB |
Output is correct |
23 |
Correct |
249 ms |
24884 KB |
Output is correct |
24 |
Correct |
40 ms |
15572 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
14940 KB |
Output is correct |
2 |
Correct |
2 ms |
14944 KB |
Output is correct |
3 |
Correct |
2 ms |
14940 KB |
Output is correct |
4 |
Correct |
2 ms |
14940 KB |
Output is correct |
5 |
Correct |
2 ms |
14992 KB |
Output is correct |
6 |
Correct |
2 ms |
14940 KB |
Output is correct |
7 |
Correct |
19 ms |
17016 KB |
Output is correct |
8 |
Correct |
20 ms |
16984 KB |
Output is correct |
9 |
Correct |
20 ms |
17116 KB |
Output is correct |
10 |
Correct |
13 ms |
15960 KB |
Output is correct |
11 |
Correct |
18 ms |
16720 KB |
Output is correct |
12 |
Correct |
7 ms |
14940 KB |
Output is correct |
13 |
Correct |
16 ms |
17004 KB |
Output is correct |
14 |
Correct |
16 ms |
16984 KB |
Output is correct |
15 |
Correct |
16 ms |
17172 KB |
Output is correct |
16 |
Correct |
17 ms |
16476 KB |
Output is correct |
17 |
Correct |
9 ms |
15448 KB |
Output is correct |
18 |
Correct |
3 ms |
14940 KB |
Output is correct |
19 |
Correct |
692 ms |
72496 KB |
Output is correct |
20 |
Correct |
687 ms |
72192 KB |
Output is correct |
21 |
Correct |
662 ms |
72136 KB |
Output is correct |
22 |
Correct |
329 ms |
33340 KB |
Output is correct |
23 |
Correct |
670 ms |
49908 KB |
Output is correct |
24 |
Correct |
180 ms |
16412 KB |
Output is correct |
25 |
Correct |
901 ms |
72128 KB |
Output is correct |
26 |
Correct |
694 ms |
72044 KB |
Output is correct |
27 |
Correct |
882 ms |
72268 KB |
Output is correct |
28 |
Correct |
518 ms |
46532 KB |
Output is correct |
29 |
Correct |
254 ms |
24880 KB |
Output is correct |
30 |
Correct |
41 ms |
15572 KB |
Output is correct |
31 |
Correct |
1069 ms |
72084 KB |
Output is correct |
32 |
Correct |
841 ms |
72244 KB |
Output is correct |
33 |
Correct |
658 ms |
72368 KB |
Output is correct |
34 |
Correct |
384 ms |
34620 KB |
Output is correct |
35 |
Correct |
641 ms |
50020 KB |
Output is correct |
36 |
Correct |
149 ms |
16468 KB |
Output is correct |
37 |
Correct |
1036 ms |
72152 KB |
Output is correct |
38 |
Correct |
1004 ms |
72012 KB |
Output is correct |
39 |
Correct |
1506 ms |
72152 KB |
Output is correct |
40 |
Correct |
506 ms |
46532 KB |
Output is correct |
41 |
Correct |
249 ms |
24884 KB |
Output is correct |
42 |
Correct |
40 ms |
15572 KB |
Output is correct |
43 |
Correct |
1319 ms |
94240 KB |
Output is correct |
44 |
Correct |
1336 ms |
94324 KB |
Output is correct |
45 |
Correct |
964 ms |
94612 KB |
Output is correct |
46 |
Correct |
406 ms |
46960 KB |
Output is correct |
47 |
Correct |
652 ms |
75576 KB |
Output is correct |
48 |
Correct |
92 ms |
16084 KB |
Output is correct |
49 |
Correct |
1508 ms |
94396 KB |
Output is correct |
50 |
Correct |
1825 ms |
94472 KB |
Output is correct |
51 |
Correct |
2671 ms |
94144 KB |
Output is correct |
52 |
Correct |
586 ms |
64560 KB |
Output is correct |
53 |
Correct |
278 ms |
28200 KB |
Output is correct |