#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef long double ld;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef stack<int> si;
typedef queue<int> qi;
typedef deque<int> di;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
#define endl '\n'
#define pb push_back
#define FOR(i,g,b) for(int i = g; i <= b; i++)
#define BACK(i,g,b) for(int i = g; i >= b; i--)
#define fastIO ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define fi first
#define se second
#define gcd __gcd
#define setmin(x,y) x=min((x),(y))
#define setmax(x,y) x=max((x),(y))
const int MAXN=1e5+5;
const long long inf=1e18;
const int MOD=1e9+7;
struct query
{
int x,y,z,idx;
query(const int& x,const int& y,const int& z,const int& idx):x(x),y(y),z(z),idx(idx){}
bool operator <(const query& other) {return z>other.z;}
};
struct stud
{
int s,t;
stud(const int& s,const int& t):s(s),t(t){}
bool operator <(const stud& other) {return s+t>other.s+other.t;}
};
vector<query> q;
vector<stud> st;
int n,m,ans[MAXN];
vector<int> xs,ys;
vector<vector<int>> node,bit;
void fakeupd(int x,int y)
{
for(;x<=m;x+=x&-x) node[x].pb(y);
}
void fakeget(int x,int y)
{
for(;x>0;x-=x&-x) node[x].pb(y);
}
void upd(int x,int yy)
{
for(;x<=xs.size();x+=x&-x) for(int y=lower_bound(node[x].begin(),node[x].end(),yy)-node[x].begin()+1;y<=node[x].size();y+=y&-y) bit[x][y-1]++;
}
int get(int x,int yy)
{
int res=0;
for(;x>0;x-=x&-x) for(int y=lower_bound(node[x].begin(),node[x].end(),yy)-node[x].begin()+1;y>0;y-=y&-y) res+=bit[x][y-1];
return res;
}
int xid(const int& x)
{
return lower_bound(xs.begin(),xs.end(),x,greater<int>())-xs.begin();
}
int yid(const int& y)
{
return lower_bound(ys.begin(),ys.end(),y,greater<int>())-ys.begin();
}
signed main()
{
fastIO
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
cin>>n>>m;
FOR(i,0,n-1) {int s,t; cin>>s>>t; st.emplace_back(s,t); xs.pb(s); ys.pb(t);}
FOR(i,0,m-1) {int x,y,z; cin>>x>>y>>z; q.emplace_back(x,y,z,i); xs.pb(x); ys.pb(y);}
sort(xs.begin(),xs.end(),greater<int>());
xs.erase(unique(xs.begin(),xs.end()),xs.end());
sort(ys.begin(),ys.end(),greater<int>());
ys.erase(unique(ys.begin(),ys.end()),ys.end());
node.resize(xs.size()+1);
bit.resize(xs.size()+1);
FOR(i,0,n-1) fakeupd(xid(st[i].s)+1,yid(st[i].t));
FOR(i,0,m-1) fakeget(xid(q[i].x)+1,yid(q[i].y));
FOR(i,1,xs.size())
{
sort(node[i].begin(),node[i].end());
node[i].erase(unique(node[i].begin(),node[i].end()),node[i].end());
bit[i].resize(node[i].size());
}
sort(st.begin(),st.end()); sort(q.begin(),q.end());
int cur=0;
FOR(i,0,m-1)
{
while(cur<n&&st[cur].s+st[cur].t>=q[i].z) {upd(xid(st[cur].s)+1,yid(st[cur].t)); cur++;}
ans[q[i].idx]=get(xid(q[i].x)+1,yid(q[i].y));
}
FOR(i,0,m-1) cout<<ans[i]<<endl;
}
Compilation message
examination.cpp: In function 'void upd(long long int, long long int)':
examination.cpp:63:8: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | for(;x<=xs.size();x+=x&-x) for(int y=lower_bound(node[x].begin(),node[x].end(),yy)-node[x].begin()+1;y<=node[x].size();y+=y&-y) bit[x][y-1]++;
| ~^~~~~~~~~~~
examination.cpp:63:104: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | for(;x<=xs.size();x+=x&-x) for(int y=lower_bound(node[x].begin(),node[x].end(),yy)-node[x].begin()+1;y<=node[x].size();y+=y&-y) bit[x][y-1]++;
| ~^~~~~~~~~~~~~~~~
examination.cpp: In function 'int main()':
examination.cpp:18:37: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
18 | #define FOR(i,g,b) for(int i = g; i <= b; i++)
......
99 | FOR(i,1,xs.size())
| ~~~~~~~~~~~~~
examination.cpp:99:2: note: in expansion of macro 'FOR'
99 | FOR(i,1,xs.size())
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
10 ms |
1748 KB |
Output is correct |
| 8 |
Correct |
9 ms |
1684 KB |
Output is correct |
| 9 |
Correct |
9 ms |
1744 KB |
Output is correct |
| 10 |
Correct |
6 ms |
1492 KB |
Output is correct |
| 11 |
Runtime error |
3 ms |
1356 KB |
Execution killed with signal 11 |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
189 ms |
68696 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
189 ms |
68696 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
10 ms |
1748 KB |
Output is correct |
| 8 |
Correct |
9 ms |
1684 KB |
Output is correct |
| 9 |
Correct |
9 ms |
1744 KB |
Output is correct |
| 10 |
Correct |
6 ms |
1492 KB |
Output is correct |
| 11 |
Runtime error |
3 ms |
1356 KB |
Execution killed with signal 11 |
| 12 |
Halted |
0 ms |
0 KB |
- |
