#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#define endl "\n"
typedef long long ll;
template<class T, class T2> inline ostream &operator <<(ostream &out, const pair<T, T2> &x) { out << x.first << " " << x.second; return out;}
template<class T, class T2> inline istream &operator >>(istream &in, pair<T, T2> &x) { in >> x.first >> x.second; return in;}
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const ll mod = 1e9 + 7;
#define out(x) "{" << (#x) << ": " << x << "} "
const ll MAX_N = 1e5 + 10;
ll a[MAX_N], b[MAX_N], s[MAX_N];
ll n, q;
ll x[MAX_N], y[MAX_N], z[MAX_N];
ll ans[MAX_N];
pair<ll, pair<ll, ll> > quer[MAX_N * 2];
struct Node {
Node *l, *r;
ll val;
ll sz, cnt;
ll prior;
Node(ll val, Node *l = nullptr, Node *r = nullptr) : val(val), sz(sz), l(l), r(r) {
this->prior = rand() + rand() << 16ll;
this->cnt = this->sz = 1;
}
};
typedef Node* pnode;
pnode tree[4 * MAX_N];
void traverse(pnode x, ll tab = 0) {
if(!x) {return;}
traverse(x->l, tab + 1);
for(ll i = 0; i < tab; i ++) {
//cerr << " ";
}
//cerr << "{" << x->val << "," << x->cnt << "}" << endl;
traverse(x->r, tab + 1);
}
ll size(pnode x) {
if(!x) {
return 0;
} else {
return x->sz;
}
}
void pull(pnode x) {
if(!x) {return;}
x->sz = size(x->l) + size(x->r) + x->cnt;
}
pnode merge(pnode l, pnode r) {
if(!l) {return r;}
if(!r) {return l;}
if(l->prior > r->prior) {
l->r = merge(l->r, r);
pull(l);
return l;
} else {
r->l = merge(l, r->l);
pull(r);
return r;
}
}
pair<pnode, pnode> split(pnode t, ll x) {
if(!t) {return {nullptr, nullptr};}
if(t->val <= x) {
auto rec = split(t->r, x);
t->r = rec.first;
pull(t);
return {t, rec.second};
} else {
auto rec = split(t->l, x);
t->l = rec.second;
pull(t);
return {rec.first, t};
}
}
void insert(pnode &t, ll x) {
auto splt = split(t, x);
auto splt2 = split(splt.first, x - 1);
if(!splt2.second) {
splt2.second = new Node(x);
} else {
splt2.second->cnt ++;
}
//cerr << "Adding " << x << endl;
//cerr << "First part" << endl;
traverse(splt2.first);
//cerr << "Second part" << endl;
traverse(splt2.second);
//cerr << "Third part" << endl;
traverse(splt.second);
//cerr << endl;
auto trp1 = merge(splt2.first, splt2.second);
auto trp = merge(trp1, splt.second);
t = trp;
}
ll getCnt(pnode &t, ll x) {
auto splt = split(t, x - 1);
//cerr << "Searching for " << x << endl;
//cerr << "First part" << endl;
traverse(splt.first);
//cerr << "Second part" << endl;
traverse(splt.second);
//cerr << endl;
ll ret = size(splt.second);
t = merge(splt.first, splt.second);
return ret;
}
void add(ll curr, ll l, ll r, ll ind, ll val) {
if(ind < l || ind > r) {
return;
}
insert(tree[curr], val);
if(l == r) {return;}
ll m = (l + r) / 2ll;
add(curr * 2, l, m, ind, val);
add(curr * 2 + 1, m + 1, r, ind, val);
}
ll cnt(ll curr, ll l, ll r, ll ind, ll val) {
if(ind <= l) {
//cerr << "Getting count for " << curr << " " << l << " " << r << " " << ind << " " << val << " --> " << getCnt(tree[curr], val) << endl;
if(getCnt(tree[curr], val) != 0) {
traverse(tree[curr], 0);
}
return getCnt(tree[curr], val);
} else if(ind > r) {
return 0;
}
ll m = (l + r) / 2ll;
return cnt(curr * 2, l, m, ind, val) + cnt(curr * 2 + 1, m + 1, r, ind, val);
}
signed main() {
//ios_base::sync_with_stdio(false); cin.tie(NULL); //cerr.tie(NULL);
vector<ll> c;
cin >> n >> q;
for(ll i = 0; i < n; i ++) {
cin >> a[i] >> b[i];
s[i] = a[i] + b[i];
c.push_back(a[i]);
c.push_back(b[i]);
c.push_back(s[i]);
}
for(ll i = 0; i < q; i ++) {
cin >> x[i] >> y[i] >> z[i];
c.push_back(x[i]);
c.push_back(y[i]);
c.push_back(z[i]);
}
sort(c.begin(), c.end());
c.resize(unique(c.begin(), c.end()) - c.begin());
for(ll i = 0; i < n; i ++) {
a[i] = lower_bound(c.begin(), c.end(), a[i]) - c.begin();
b[i] = lower_bound(c.begin(), c.end(), b[i]) - c.begin();
s[i] = lower_bound(c.begin(), c.end(), s[i]) - c.begin();
quer[i] = {a[i], {1, i}};
}
for(ll i = 0; i < q; i ++) {
x[i] = lower_bound(c.begin(), c.end(), x[i]) - c.begin();
y[i] = lower_bound(c.begin(), c.end(), y[i]) - c.begin();
z[i] = lower_bound(c.begin(), c.end(), z[i]) - c.begin();
quer[n + i] = {x[i], {-1, i}};
}
sort(quer, quer + n + q);
for(ll i = n + q - 1; i >= 0; i --) {
if(quer[i].second.first == 1) {
ll ind = quer[i].second.second;
//cerr << "Adding " << b[ind] << " " << s[ind] << endl;
add(1, 0, MAX_N - 1, b[ind], s[ind]);
} else {
ll ind = quer[i].second.second;
//cerr << "Query " << ind << endl;
ans[ind] = cnt(1, 0, MAX_N - 1, y[ind], z[ind]);
}
}
for(ll i = 0; i < q; i ++) {
cout << ans[i] << endl;
}
return 0;
}
Compilation message
examination.cpp: In constructor 'Node::Node(ll, Node*, Node*)':
examination.cpp:25:8: warning: 'Node::sz' will be initialized after [-Wreorder]
25 | ll sz, cnt;
| ^~
examination.cpp:23:11: warning: 'Node* Node::l' [-Wreorder]
23 | Node *l, *r;
| ^
examination.cpp:28:5: warning: when initialized here [-Wreorder]
28 | Node(ll val, Node *l = nullptr, Node *r = nullptr) : val(val), sz(sz), l(l), r(r) {
| ^~~~
examination.cpp:28:5: warning: 'Node::sz' is initialized with itself [-Winit-self]
examination.cpp:29:30: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
29 | this->prior = rand() + rand() << 16ll;
| ~~~~~~~^~~~~~~~
examination.cpp: In constructor 'Node::Node(ll, Node*, Node*)':
examination.cpp:28:71: warning: '*<unknown>.Node::sz' is used uninitialized in this function [-Wuninitialized]
28 | Node(ll val, Node *l = nullptr, Node *r = nullptr) : val(val), sz(sz), l(l), r(r) {
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
332 KB |
Output is correct |
| 5 |
Correct |
1 ms |
332 KB |
Output is correct |
| 6 |
Correct |
1 ms |
332 KB |
Output is correct |
| 7 |
Correct |
313 ms |
4560 KB |
Output is correct |
| 8 |
Correct |
312 ms |
4712 KB |
Output is correct |
| 9 |
Correct |
310 ms |
4596 KB |
Output is correct |
| 10 |
Correct |
863 ms |
4272 KB |
Output is correct |
| 11 |
Correct |
334 ms |
4448 KB |
Output is correct |
| 12 |
Incorrect |
18 ms |
968 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3064 ms |
30724 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3064 ms |
30724 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
332 KB |
Output is correct |
| 5 |
Correct |
1 ms |
332 KB |
Output is correct |
| 6 |
Correct |
1 ms |
332 KB |
Output is correct |
| 7 |
Correct |
313 ms |
4560 KB |
Output is correct |
| 8 |
Correct |
312 ms |
4712 KB |
Output is correct |
| 9 |
Correct |
310 ms |
4596 KB |
Output is correct |
| 10 |
Correct |
863 ms |
4272 KB |
Output is correct |
| 11 |
Correct |
334 ms |
4448 KB |
Output is correct |
| 12 |
Incorrect |
18 ms |
968 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
