#include <bits/stdc++.h>
using namespace std;
#define name "aaaaaa"
using ll = long long;
void file(){
ios_base::sync_with_stdio(0); cin.tie(0);
if(fopen(name".inp", "r")) {
freopen(name".inp", "r", stdin);
freopen(name".out", "w", stdout);
}
}
struct node {
int x, y, z, i, val;
};
const int maxn = 3e5 + 5;
struct BIT {
int b[maxn], n;
void build(int _n) {
n = _n;
fill(b, b + n + 1, 0);
}
int lowbit(int x){
return x & (-x);
}
void update(int x, int v){
for(int i = x; i <= n; i += lowbit(i)){
b[i] += v;
}
}
int query(int x) {
int ans = 0;
for(int i = x; i > 0; i -= lowbit(i)){
ans += b[i];
}
return ans;
}
} bit;
vector<node> v;
int n, q, ans[maxn];
void cdq(int l, int r) {
if(l == r) return;
int m = (l + r) / 2;
cdq(l, m); cdq(m + 1, r);
int a = l, b = m + 1, sum = 0;
vector<pair<int, int>> record;
vector<node> tmp;
while(a <= m && b <= r){
if(v[a].y >= v[b].y){
int add = v[a].val;
bit.update(v[a].z, add), sum += add, record.push_back({v[a].z, add}), tmp.push_back(v[a]);
a++;
}else{
ans[v[b].i] += sum - bit.query(v[b].z - 1), tmp.push_back(v[b]);
b++;
}
}
while(a <= m){
tmp.push_back(v[a]);
a++;
}
while(b <= r){
ans[v[b].i] += sum - bit.query(v[b].z - 1), tmp.push_back(v[b]);
b++;
}
for(int i = l; i <= r; i++){
v[i] = tmp[i - l];
}
for(auto i : record) bit.update(i.first, -i.second);
}
bool comp(node a, node b){
if(a.x == b.x && a.y == b.y && a.z == b.z && a.val == 1 && b.val == 0) return true;
return (a.x == b.x ? (a.y == b.y ? a.z < b.z : a.y < b.y) : a.x > b.x);
}
map<int, int> mp;
void solve() {
cin >> n >> q;
for(int i = 0; i < n; i++){
int a, b, c;
cin >> a >> b;
c = a + b;
mp[a] = true;
mp[b] = true;
mp[c] = true;
v.push_back({a, b, c, i, 1});
}
for(int i = n; i < n + q; i++){
int x, y, z;
cin >> x >> y >> z;
mp[x] = true;
mp[y] = true;
mp[z] = true;
v.push_back({x, y, z, i, 0});
}
int id = 1;
for(auto i : mp){
mp[i.first] = id;
id++;
}
for(int i = 0; i < v.size(); i++){
v[i].x = mp[v[i].x];
v[i].y = mp[v[i].y];
v[i].z = mp[v[i].z];
}
bit.build(id);
sort(v.begin(), v.end(), comp);
cdq(0, n + q - 1);
for(int i = n; i < n + q; i++) cout << ans[i] << '\n';
}
int main() {
file();
solve();
}
Compilation message
examination.cpp: In function 'void solve()':
examination.cpp:110:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
110 | for(int i = 0; i < v.size(); i++){
| ~~^~~~~~~~~~
examination.cpp: In function 'void file()':
examination.cpp:9:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
9 | freopen(name".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:10:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
10 | freopen(name".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 6 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 7 |
Correct |
12 ms |
3724 KB |
Output is correct |
| 8 |
Correct |
12 ms |
3660 KB |
Output is correct |
| 9 |
Correct |
12 ms |
3712 KB |
Output is correct |
| 10 |
Correct |
10 ms |
3388 KB |
Output is correct |
| 11 |
Incorrect |
8 ms |
3388 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
433 ms |
22660 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
433 ms |
22660 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 6 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 7 |
Correct |
12 ms |
3724 KB |
Output is correct |
| 8 |
Correct |
12 ms |
3660 KB |
Output is correct |
| 9 |
Correct |
12 ms |
3712 KB |
Output is correct |
| 10 |
Correct |
10 ms |
3388 KB |
Output is correct |
| 11 |
Incorrect |
8 ms |
3388 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
