#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
#include <numeric>
#include <ctime>
#include <bitset>
#include <complex>
#include <random>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T>
using flex_set = tree<T, null_type, greater<T>, rb_tree_tag, tree_order_statistics_node_update>;
struct Block {
int sz;
flex_set<pair<int, int>> kek;
int solve(int x) {
return sz - kek.order_of_key(make_pair(x, -1));
}
void insert(int x) {
sz++;
kek.insert(make_pair(x, sz));
}
Block() {}
};
struct UltraFenw {
int n;
vector<Block> f;
int cnt(int r, int x) {
int ans = 0;
for (int i = r; i >= 0; i = (i & (i + 1)) - 1) {
ans += f[i].solve(x);
}
return ans;
}
int cnt(int l, int r, int x) {
return cnt(r, x) - cnt(l - 1, x);
}
void insert(int pos, int val) {
for (int i = pos; i < n; i = i | (i + 1)) {
f[i].insert(val);
}
}
UltraFenw(int n_) {
n = n_;
f.resize(n);
}
};
struct Query {
int a, b, c;
int ind;
Query(int a_, int b_, int c_, int ind_) {
a = a_;
b = b_;
c = c_;
ind = ind_;
};
bool operator<(const Query &other) const {
return c < other.c;
}
};
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, q;
cin >> n >> q;
vector<pair<int, int>> a(n);
for (auto &t : a) cin >> t.first >> t.second;
sort(a.begin(), a.end());
vector<int> f(n);
vector<int> s(n);
vector<int> sm(n);
for (int i = 0; i < n; i++) {
tie(f[i], s[i]) = a[i];
sm[i] = f[i] + s[i];
}
UltraFenw fn(n);
vector<Query> qs;
for (int i = 0; i < q; i++) {
int x, y, z;
cin >> x >> y >> z;
qs.push_back(Query(x, y, z, i));
}
sort(qs.rbegin(), qs.rend());
vector<int> ind(n);
iota(ind.begin(), ind.end(), 0);
sort(ind.rbegin(), ind.rend(), [&](int i, int j) {
return sm[i] < sm[j];
});
int pnt = 0;
vector<int> ans(q);
for (auto t : qs) {
while (pnt < n && sm[ind[pnt]] >= t.c) {
fn.insert(ind[pnt], s[ind[pnt]]);
pnt++;
}
int i = lower_bound(f.begin(), f.end(), t.a) - f.begin();
ans[t.ind] = fn.cnt(i, n - 1, t.b);
}
for (auto t : ans) {
cout << t << ' ';
}
cout << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1818 ms |
70480 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1818 ms |
70480 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
