#include <bits/stdc++.h>
using namespace std;
#define MAXN 100005
#define MAXBIT 30
typedef pair<int,int> pii;
struct node {node* nula;node* kec;int cnt;};
void update(node* root,int val)
{
node* now = root;
root->cnt++;
for(int i = MAXBIT-1; i >= 0; i--)
{
if(val & (1<<i))
{
if(now->kec == NULL)now->kec=new node();
now=now->kec;
}
else
{
if(now->nula == NULL)now->nula=new node();
now=now->nula;
}
now->cnt++;
}
}
int query(node* root,int val)
{
int ret=0;
node* now = root;
for(int i = MAXBIT-1; i >= 0; i--)
{
if(val & (1<<i))
{
if(now->kec == NULL)return ret;
now=now->kec;
}
else
{
if(now->kec != NULL)ret += now->kec->cnt;
if(now->nula == NULL)return ret;
now=now->nula;
}
}
ret += now->cnt;
return ret;
}
node* tree[4*MAXN];
void update(int nod,int left,int right,int idx,int val)
{
if(left <= idx && idx <= right)
{
if(tree[nod]==NULL)tree[nod]=new node();
//if(val==1)cout << nod << " " << left << " " << right << " " << idx << "\n";
update(tree[nod],val);
}
else return;
if(left==right)return ;
int mid=(left+right)>>1;
update(nod*2,left,mid,idx,val);
update(nod*2+1,mid+1,right,idx,val);
}
int query(int nod,int left,int right,int l,int r,int x)
{
if(left > right || left > r || l > right || l > r)return 0;
if(left >= l && right <= r)
{
if(tree[nod]==NULL)return 0;
return query(tree[nod],x);
}
int mid=(left+right)>>1;
return query(nod*2,left,mid,l,r,x)+query(nod*2+1,mid+1,right,l,r,x);
}
vector <int> order_a;
vector <int> order_b;
map <int,int> mp;
int ans[MAXN];
int s[MAXN];
int t[MAXN];
bool cmp(int x,int y){return s[x] < s[y];}
bool cmp0(int x,int y){return t[x] < t[y];}
struct upit
{
int x,y,z,id;
};
bool cmp2(upit x,upit y)
{
return x.x<y.x;
}
vector <upit> queries;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n,q;
cin >> n >> q;
for(int i = 1; i <= n; i++)
{
cin >> s[i] >> t[i];
order_a.push_back(i);
order_b.push_back(i);
}
sort(order_a.begin(),order_a.end(),cmp);
sort(order_b.begin(),order_b.end(),cmp0);
for(int i = 0; i < order_b.size(); i++)mp[order_b[i]]=i+1;
for(int i = 0; i < q; i++)
{
int x,y,z;
cin >> x >> y >> z;
upit u;
u.x=x;u.y=y;u.z=z;u.id=i;
queries.push_back(u);
}
sort(queries.begin(),queries.end(),cmp2);
int now=n;
for(int i = q-1; i >= 0; i--)
{
while(now-1 >= 0 && s[order_a[now-1]] >= queries[i].x)
{
now--;
update(1,1,n,mp[order_a[now]],s[order_a[now]]+t[order_a[now]]);
}
int lo=0,hi=n-1,mid=lo+hi>>1,r=n;
while(lo<=hi)
{
if(t[order_b[mid]]>=queries[i].y)
{
r=mid;
hi=mid-1;
}
else lo=mid+1;
mid=lo+hi>>1;
}
r++;
if(r>n)continue;
ans[queries[i].id]=query(1,1,n,r,n,queries[i].z);
}
for(int i = 0; i < q; i++)
{
cout << ans[i] << " ";
}
return 0;
}
Compilation message
examination.cpp: In function 'int main()':
examination.cpp:112:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < order_b.size(); i++)mp[order_b[i]]=i+1;
~~^~~~~~~~~~~~~~~~
examination.cpp:130:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int lo=0,hi=n-1,mid=lo+hi>>1,r=n;
~~^~~
examination.cpp:139:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
mid=lo+hi>>1;
~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Correct |
2 ms |
384 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3085 ms |
623956 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3085 ms |
623956 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Correct |
2 ms |
384 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
