#include <bits/stdc++.h>
#define int long long
#define sqr(x) ((x) * (x))
using namespace std;
typedef pair<int, int> pi;
typedef pair<int, pi> ppi;
const int mod = 1e9+7;
struct QUERY {
int a, b, c;
int id;
};
int SQRT;
bool cmp(QUERY a, QUERY b) {
a.a /= SQRT;
a.b /= SQRT;
a.c /= SQRT;
b.a /= SQRT;
b.b /= SQRT;
b.c /= SQRT;
if(a.a != b.a)
return a.a < b.a;
else
return a.b < b.b;
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
#endif
int n, q;
cin >> n >> q;
SQRT = sqrt((n+q)*3);
vector<QUERY> v(n);
vector<int> a;
for(int i = 0; i < n; i++) {
cin >> v[i].a >> v[i].b;
v[i].c = v[i].a + v[i].b;
a.push_back(v[i].a);
a.push_back(v[i].b);
a.push_back(v[i].c);
}
vector<QUERY> qu(q);
for(int i = 0; i < q; i++) {
cin >> qu[i].a >> qu[i].b >> qu[i].c;
qu[i].id = i;
a.push_back(qu[i].a);
a.push_back(qu[i].b);
a.push_back(qu[i].c);
}
sort(a.begin(), a.end());
for(int i = 0; i < q; i++) {
int pos = lower_bound(a.begin(), a.end(), qu[i].a) - a.begin();
qu[i].a = pos;
a[pos]--;
pos = lower_bound(a.begin(), a.end(), qu[i].b) - a.begin();
qu[i].b = pos;
a[pos]--;
pos = lower_bound(a.begin(), a.end(), qu[i].c) - a.begin();
qu[i].c = pos;
a[pos]--;
}
for(int i = 0; i < n; i++) {
int pos = lower_bound(a.begin(), a.end(), v[i].a) - a.begin();
v[i].a = pos;
a[pos]--;
pos = lower_bound(a.begin(), a.end(), v[i].b) - a.begin();
v[i].b = pos;
a[pos]--;
pos = lower_bound(a.begin(), a.end(), v[i].c) - a.begin();
v[i].c = pos;
a[pos]--;
}
vector<int> v1(a.size(), -1);
vector<int> v2(a.size(), -1);
vector<int> v3(a.size(), -1);
for(int i = 0; i < n; i++) {
int j1 = v[i].a;
int j2 = v[i].b;
int j3 = v[i].c;
v1[j1] = i;
v2[j2] = i;
v3[j3] = i;
}
vector<int> pass_cnt(n+1);
int number_pass = 0;
sort(qu.begin(), qu.end(), cmp);
int a1 = a.size();
int b1 = a.size();
int c1 = a.size();
vector<int> ans(q);
for(int i = 0; i < q; i++) {
int a2 = qu[i].a;
int b2 = qu[i].b;
int c2 = qu[i].c;
while(a1 < a2) {
int j = v1[a1];
if(j != -1) {
pass_cnt[j]--;
if(pass_cnt[j] == 2)
number_pass--;
}
a1++;
}
while(b1 < b2) {
int j = v2[b1];
if(j != -1) {
pass_cnt[j]--;
if(pass_cnt[j] == 2)
number_pass--;
}
b1++;
}
while(c1 < c2) {
int j = v3[c1];
if(j != -1) {
pass_cnt[j]--;
if(pass_cnt[j] == 2)
number_pass--;
}
c1++;
}
while(a1 > a2) {
a1--;
int j = v1[a1];
if(j != -1) {
pass_cnt[j]++;
if(pass_cnt[j] == 3)
number_pass++;
}
}
while(b1 > b2) {
b1--;
int j = v2[b1];
if(j != -1) {
pass_cnt[j]++;
if(pass_cnt[j] == 3)
number_pass++;
}
}
while(c1 > c2) {
c1--;
int j = v3[c1];
if(j != -1) {
pass_cnt[j]++;
if(pass_cnt[j] == 3)
number_pass++;
}
}
ans[qu[i].id] = number_pass;
}
for(int i : ans)
cout << i << "\n";
}
Compilation message
examination.cpp: In function 'int32_t main()':
examination.cpp:31:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
31 | freopen("input.txt", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2925 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3055 ms |
1048576 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3055 ms |
1048576 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2925 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
