#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<int, int>;
#define foru(i, l, r) for(int i=(l); i<=(r); ++i)
#define ford(i, l, r) for(int i=(l; i>=(r); --i)
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)x.size()
#define fi first
#define se second
#define C make_pair
using dt = pair<ii, int>;
const int N = 2e5+5;
const int INF = 1e9;
const int SQRT = sqrt(N);
int debug = 0;
struct trie {
struct node {
int nxt[2], cnt = 0;
node() { nxt[0] = nxt[1] = -1; cnt = 0; }
};
vector<node> trie;
void built() {
trie.push_back(node());
}
void add(int num) {
for(int i=30, cur=0; i>=0; --i) {
int bit = num>>i&1;
if (trie[cur].nxt[bit] == -1) {
trie[cur].nxt[bit] = trie.size();
trie.push_back(node());
}
cur = trie[cur].nxt[bit];
trie[cur].cnt += 1;
}
}
int query(int val) {
int ans = 0, cur = 0;
for(int i=30; i>=0; --i) {
int bit = val>>i&1;
if (bit == 1) cur = trie[cur].nxt[1];
else {
if (trie[cur].nxt[1] != -1) ans += trie[trie[cur].nxt[1]].cnt;
cur = trie[cur].nxt[0];
}
if (cur == -1) return ans;
}
assert(cur != -1);
return ans + trie[cur].cnt;
}
};
int n, ny, q, ret[N];
int qx[N], qy[N], qz[N];
vector<int> vy;
vector<ii> a(N);
vector<dt> evts;
vector<trie> bit(N);
bool cmp(dt a, dt b) {
if (a.fi.fi != b.fi.fi) return a.fi.fi > b.fi.fi;
return a.se < b.se;
}
int pos(int val) {
int id = upper_bound(all(vy), val) - vy.begin();
return id;
}
void upd(int i, int v) {
for(i=ny-i+1; i<=ny; i+=i&-i) bit[i].add(v);
}
int query(int i, int v) {
int ans = 0;
for(i=ny-i+1; i>0; i-=i&-i) ans += bit[i].query(v);
return ans;
}
void solve() {
cin >> n >> q;
for(int i=1; i<=n; ++i) {
cin >> a[i].fi >> a[i].se;
vy.push_back(a[i].se);
evts.push_back(C(C(a[i].fi, i), 0));
}
for(int i=1; i<=q; ++i) {
int x, y, z;
cin >> x >> y >> z;
qx[i] = x; qy[i] = y; qz[i] = z;
vy.push_back(y);
evts.push_back(C(C(x, i), 1));
}
sort(all(evts), cmp);
sort(all(vy));
vy.resize(unique(all(vy)) - vy.begin());
ny = vy.size();
for(int x : vy) cout << x << " ";
cout << "\n";
for(int i=0; i<=ny; ++i) {
bit[i].built();
}
// upd(3, 120);
// upd(6, 140);
// cout << bit[3].query(80);
// cout << query(5, 80) << "\n";
for(auto e : evts) {
// cout << pos(10) << "\n";
// cout << e.fi.fi << " " << e.se << "\n";
if (e.se == 0) {
int i = e.fi.se;
upd(pos(a[i].se), a[i].fi + a[i].se);
// cout << "update pos " << pos(a[i].se) << " value " << a[i].fi + a[i].se << "\n";
} else {
int i = e.fi.se;
int val = qx[i] + qy[i] + max(0, qz[i] - (qx[i] + qy[i]));
// assert(pos(qy[i]) <= ny);
ret[i] = query(pos(qy[i]), val);
// cout << "query pos " << pos(qy[i]) << " greater than " << val << "\n";
}
}
for(int i=1; i<=q; ++i) {
cout << ret[i] << "\n";
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
if (fopen("input.inp", "r")) {
freopen("input.inp", "r", stdin);
freopen("input.out", "w", stdout);
}
solve();
}
Compilation message
examination.cpp: In function 'int main()':
examination.cpp:148:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
148 | freopen("input.inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:149:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
149 | freopen("input.out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
6612 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
660 ms |
160676 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
660 ms |
160676 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
6612 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
