#include "bits/stdc++.h"
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif
using ll = long long;
using pii = pair<int, int>;
#define F first
#define S second
#define sz(x) (int)((x).size())
#define all(x) (x).begin(), (x).end()
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll get_rand(ll l, ll r) {
assert(l <= r);
return uniform_int_distribution<ll> (l, r)(rng);
}
struct Fenwick{
#define gb(x) (x) & -(x)
int n;
vector<ll> bit;
void init(int _n){
n = _n;
bit.resize(n + 2, 0);
}
void upd(int x, ll val){
if(x == 0)
return;
for(; x <= n; x += gb(x))
bit[x] += val;
}
ll get(int l, int r){
ll res = 0;
--l;
for(; r; r -= gb(r)) res += bit[r];
for(; l; l -= gb(l)) res -= bit[l];
return res;
}
};
struct Point{
int x, y, z, id;
bool operator < (const Point &o){ return x == o.x ? (y == o.y ? z >= o.z : y >= o.y) : x >= o.x; }
};
const int N = 2e5 + 3;
int n, q, res[N];
vector<Point> p;
vector<int> xx;
Fenwick fen;
void cdq(int l, int r){
if(l == r) return;
int mid = (l + r) >> 1;
cdq(l, mid); cdq(mid + 1, r);
vector<Point> tmp;
vector<int> ops;
int a = l, b = mid + 1;
while(a <= mid and b <= r){
if(p[a].y >= p[b].y){
fen.upd(p[a].z, 1);
ops.push_back(p[a].z);
tmp.push_back(p[a++]);
}
else{
if(p[b].id >= 0)
res[p[b].id] += fen.get(p[b].z, N);
tmp.push_back(p[b++]);
}
}
while(a <= l)
tmp.push_back(p[a++]);
while(b <= r){
if(p[b].id >= 0)
res[p[b].id] += fen.get(p[b].z, N);
tmp.push_back(p[b++]);
}
for(int i = l; i <= r; ++i)
p[i] = tmp[i - l];
for(int x : ops)
fen.upd(x, -1);
vector<Point>().swap(tmp);
vector<int>().swap(ops);
}
void solve(){
cin >> n >> q;
for(int i = 0; i < n; ++i){
int s, t;
cin >> s >> t;
p.push_back({s, t, s + t, -1});
xx.push_back(s + t);
}
for(int i = 0; i < q; ++i){
int a, b, c;
cin >> a >> b >> c;
p.push_back({a, b, c, i});
xx.push_back(c);
}
sort(all(xx));
xx.resize(unique(all(xx)) - xx.begin());
for(auto &[x, y, z, id] : p)
z = lower_bound(all(xx), z) - xx.begin() + 1;
sort(all(p));
fen.init(N);
cdq(0, sz(p) - 1);
for(int i = 0; i < q; ++i)
cout << res[i] << '\n';
}
int32_t main() {
cin.tie(nullptr)->sync_with_stdio(0);
#define task "troll"
if(fopen(task".inp", "r")){
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
int test = 1;
// cin >> test;
for(int i = 1; i <= test; ++i){
// cout << "Case #" << i << ": ";
solve();
}
#ifdef LOCAL
cerr << "\n[Time]: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms.\n";
#endif
return 0;
}
Compilation message
examination.cpp: In function 'int32_t main()':
examination.cpp:131:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
131 | freopen(task".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:132:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
132 | freopen(task".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1884 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
67 ms |
18172 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
67 ms |
18172 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1884 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
