#include<bits/stdc++.h>
#define ll int
using namespace std;
const int N = 1e5+1;
const ll INF = (1LL<<20);
ll n, q, s[N], t[N];
vector<int> priorities;
struct Treap {
ll key, prior, cnt, num=1;
Treap *l=NULL, *r=NULL;
};
int cnt(Treap* it) {
return it? it->cnt:0;
}
void upd_cnt(Treap* it) {
if(it) {
it->cnt = cnt(it->l) + cnt(it->r) + it->num;
}
}
void split(Treap* T, int key, Treap* &l, Treap* &r) {
if(!T) {
l = r = NULL;
return;
}
if(key < T->key) {
split(T->l, key, l, T->l);
r = T;
}
else {
split(T->r, key, T->r, r);
l = T;
}
upd_cnt(T);
}
bool find(Treap* &T, int key) {
if(!T) {
return false;
}
if(T->key == key) {
T->num ++;
upd_cnt(T);
return true;
}
else if(key < T->key) {
bool found = find(T->l, key);
upd_cnt(T);
return found;
}
else {
bool found = find(T->r, key);
upd_cnt(T);
return found;
}
}
void insert(Treap* &T, Treap* it) {
if(!T) {
T = it;
return;
}
if(it->prior > T->prior) {
split(T, it->key, it->l, it->r);
T = it;
}
else {
insert(it->key < T->key? T->l:T->r, it);
}
upd_cnt(T);
}
int query(Treap* cur, ll x) {
if(!cur) return 0;
if(x == cur->key) {
return cnt(cur) - cnt(cur->r);
}
if(x < cur->key) {
return query(cur->l, x);
}
else {
return query(cur->r, x) + cnt(cur) - cnt(cur->r);
}
}
struct Node {
Treap* treap[3] = {NULL, NULL, NULL};
ll l, r;
Node* ls=NULL;
Node* rs=NULL;
void push() {
if(!ls) {
ll mid = (l+r)/2;
ls = new Node;
rs = new Node;
ls->l = l;
ls->r = mid;
rs->l = mid+1;
rs->r=r;
}
}
};
Node* root = NULL;
int Query(ll l, ll r, ll x, int which_treap, Node* cur=root) {
if(cur->l > r || cur->r < l) {
return 0;
}
if(l<=cur->l && r>=cur->r) {
ll tmp = cnt(cur->treap[which_treap]) - query(cur->treap[which_treap], x-1);
return tmp;
}
cur->push();
return Query(l, r, x, which_treap, cur->ls)+Query(l, r, x, which_treap, cur->rs);
}
void Insert(ll x, ll y, int which_treap, Node* cur=root) {
if(cur->l>x || cur->r<x) return;
Treap* it = new Treap;
it->key = y;
it->prior = priorities.back();
it->cnt = 1;
if(!find(cur->treap[which_treap], y)) {
insert(cur->treap[which_treap], it);
}
if(cur->l==cur->r && cur->l==x) {
return;
}
cur->push();
Insert(x, y, which_treap, cur->ls);
Insert(x, y, which_treap, cur->rs);
}
int main() {
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n>>q;
root = new Node;
root->l = 0;
root->r = INF-1;
for(int i=1; i<=n; ++i) {
priorities.push_back(i);
}
random_shuffle(priorities.begin(), priorities.end());
for(int i=0; i<n; ++i) {
cin>>s[i]>>t[i];
Insert(s[i], t[i], 0);
Insert(s[i], s[i]+t[i], 1);
Insert(t[i], s[i]+t[i], 2);
priorities.pop_back();
}
while(q--) {
int x, y, z;
cin>>x>>y>>z;
if(z > x+y) {
cout<<Query(x, INF-1, z, 1) - Query(0, y-1, z, 2)<<'\n';
}
else {
cout<<Query(x, INF-1, y, 0)<<'\n';
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| 3 |
Correct |
5 ms |
384 KB |
Output is correct |
| 4 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3097 ms |
226372 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3097 ms |
226372 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| 3 |
Correct |
5 ms |
384 KB |
Output is correct |
| 4 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
