This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define gibon ios::sync_with_stdio(false); cin.tie(0);
using namespace std;
#define fir first
#define sec second
#define ll long long
#define pii pair<int, int>
const int mxN=103000;
typedef struct pro{
ll a, b, c;
}pro;
typedef struct qry{
int x, sy, ey, idx, typ;
}qry;
int N, Q;
pro T[mxN];
pii A[mxN];
vector <int> coorx, coory, coorxy;
vector <int> xy;
int ans[mxN];
vector <qry> v;
vector <pii> swp;
int X, Y;
int seg[4*mxN];
bool cmp1(qry p, qry q)
{
return p.x<q.x;
}
bool cmp2(pii a, pii b)
{
return a.fir<b.fir;
}
void init(int idx, int s, int e)
{
seg[idx]=0;
if(s==e) return;
int mid=(s+e)/2;
init(2*idx, s, mid);
init(2*idx+1, mid+1, e);
}
int solv(int idx, int s1, int e1, int s2, int e2)
{
if(s2>e1 || s1>e2) return 0;
if(s2<=s1 && e1<=e2) return seg[idx];
int mid=(s1+e1)/2;
return solv(2*idx, s1, mid, s2, e2)+solv(2*idx+1, mid+1, e1, s2, e2);
}
void upd(int idx, int s, int e, int pos)
{
if(pos<s || pos>e) return;
seg[idx]++;
if(s==e) return;
int mid=(s+e)/2;
upd(2*idx, s, mid, pos);
upd(2*idx+1, mid+1, e, pos);
}
void make_coor()
{
for(int i=0;i<N;i++) coorx.push_back(A[i].fir), coory.push_back(A[i].sec);
for(int i=0;i<N;i++) coorxy.push_back(A[i].fir+A[i].sec);
coorx.push_back(1000000007);
coory.push_back(1000000007);
coorx.push_back(-2);
coory.push_back(-2);
coorxy.push_back(2000000007);
coorxy.push_back(-2);
sort(coorx.begin(), coorx.end()); sort(coory.begin(), coory.end());
sort(coorxy.begin(), coorxy.end());
coorx.erase(unique(coorx.begin(), coorx.end()), coorx.end());
coory.erase(unique(coory.begin(), coory.end()), coory.end());
coorxy.erase(unique(coorxy.begin(), coorxy.end()), coorxy.end());
X=coorx.size(), Y=coory.size();
}
int main()
{
gibon
cin >> N >> Q;
for(int i=0;i<N;i++) cin >> A[i].fir >> A[i].sec;
for(int i=0;i<Q;i++) cin >> T[i].a >> T[i].b >> T[i].c;
make_coor();
for(int i=0;i<Q;i++)
{
int nx=lower_bound(coorx.begin(), coorx.end(), T[i].a)-coorx.begin();
int ny=lower_bound(coory.begin(), coory.end(), T[i].b)-coory.begin();
//printf("i=%d, nx=%d, ny=%d\n", i, nx, ny);
v.push_back({X-1, ny, Y-1, i, 1});
v.push_back({nx-1, ny, Y-1, i, -1});
if(T[i].a+T[i].b>=T[i].c) continue;
v.push_back({nx-1, 0, ny-1, i, -1});
}
sort(v.begin(), v.end(), cmp1);
init(1, 0, Y-1);
for(int i=0;i<N;i++)
{
int nx=lower_bound(coorx.begin(), coorx.end(), A[i].fir)-coorx.begin();
int ny=lower_bound(coory.begin(), coory.end(), A[i].sec)-coory.begin();
swp.push_back({nx, ny});
}
sort(swp.begin(), swp.end(), cmp2);
//for(qry ele : v) printf("ele=%d, %d, %d, %d, %d\n", ele.x, ele.sy, ele.ey, ele.idx, ele.typ);
int cur=0;
for(int i=0;i<N;i++)
{
while(cur!=v.size() && v[cur].x<swp[i].fir)
{
ans[v[cur].idx]+=solv(1, 0, Y-1, v[cur].sy, v[cur].ey)*v[cur].typ;
cur++;
}
upd(1, 0, Y-1, swp[i].sec);
}
while(cur!=v.size())
{
ans[v[cur].idx]+=solv(1, 0, Y-1, v[cur].sy, v[cur].ey)*v[cur].typ;
cur++;
}
//for(int i=0;i<Q;i++) printf("ans[%d]=%d\n", i, ans[i]);
///-------------------------
v.clear();
for(int i=0;i<Q;i++)
{
if(T[i].a+T[i].b>=T[i].c) continue;
int ny=lower_bound(coory.begin(), coory.end(), T[i].b)-coory.begin();
int nxy=lower_bound(coorxy.begin(), coorxy.end(), T[i].c)-coorxy.begin()-1;
v.push_back({nxy, ny, Y-1, i, -1});
}
sort(v.begin(), v.end(), cmp1);
swp.clear();
for(int i=0;i<N;i++)
{
int nxy=lower_bound(coorxy.begin(), coorxy.end(), A[i].fir+A[i].sec)-coorxy.begin();
int ny=lower_bound(coory.begin(), coory.end(), A[i].sec)-coory.begin();
swp.push_back({nxy, ny});
}
sort(swp.begin(), swp.end(), cmp2);
init(1, 0, Y-1);
cur=0;
for(int i=0;i<N;i++)
{
while(cur!=v.size() && v[cur].x<swp[i].fir)
{
ans[v[cur].idx]+=solv(1, 0, Y-1, v[cur].sy, v[cur].ey)*v[cur].typ;
cur++;
}
upd(1, 0, Y-1, swp[i].sec);
}
while(cur!=v.size())
{
ans[v[cur].idx]+=solv(1, 0, Y-1, v[cur].sy, v[cur].ey)*v[cur].typ;
cur++;
}
//for(int i=0;i<Q;i++) printf("ans[%d]=%d\n", i, ans[i]);
///--------------------------
v.clear();
for(int i=0;i<Q;i++)
{
if(T[i].a+T[i].b>=T[i].c) continue;
int nxy=lower_bound(coorxy.begin(), coorxy.end(), T[i].c)-coorxy.begin()-1;
int nx=lower_bound(coorx.begin(), coorx.end(), T[i].a)-coorx.begin();
v.push_back({nxy, nx, X-1, i, -1});
}
sort(v.begin(), v.end(), cmp1);
swp.clear();
for(int i=0;i<N;i++)
{
int nxy=lower_bound(coorxy.begin(), coorxy.end(), A[i].fir+A[i].sec)-coorxy.begin();
int nx=lower_bound(coorx.begin(), coorx.end(), A[i].fir)-coorx.begin();
swp.push_back({nxy, nx});
}
sort(swp.begin(), swp.end(), cmp2);
init(1, 0, X-1);
cur=0;
for(int i=0;i<N;i++)
{
while(cur!=v.size() && v[cur].x<swp[i].fir)
{
ans[v[cur].idx]+=solv(1, 0, X-1, v[cur].sy, v[cur].ey)*v[cur].typ;
cur++;
}
upd(1, 0, X-1, swp[i].sec);
}
while(cur!=v.size())
{
ans[v[cur].idx]+=solv(1, 0, X-1, v[cur].sy, v[cur].ey)*v[cur].typ;
cur++;
}
//for(int i=0;i<Q;i++) printf("ans[%d]=%d\n", i, ans[i]);
///-------------------
for(int i=0;i<N;i++) xy.push_back(A[i].fir+A[i].sec);
sort(xy.begin(), xy.end());
for(int i=0;i<Q;i++)
{
if(T[i].a+T[i].b>=T[i].c) continue;
ans[i]+=lower_bound(xy.begin(), xy.end(), T[i].c)-xy.begin();
}
for(int i=0;i<Q;i++) cout << ans[i] << '\n';
}
Compilation message (stderr)
examination.cpp: In function 'int main()':
examination.cpp:104:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<qry>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
104 | while(cur!=v.size() && v[cur].x<swp[i].fir)
| ~~~^~~~~~~~~~
examination.cpp:111:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<qry>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
111 | while(cur!=v.size())
| ~~~^~~~~~~~~~
examination.cpp:139:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<qry>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
139 | while(cur!=v.size() && v[cur].x<swp[i].fir)
| ~~~^~~~~~~~~~
examination.cpp:146:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<qry>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
146 | while(cur!=v.size())
| ~~~^~~~~~~~~~
examination.cpp:174:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<qry>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
174 | while(cur!=v.size() && v[cur].x<swp[i].fir)
| ~~~^~~~~~~~~~
examination.cpp:181:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<qry>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
181 | while(cur!=v.size())
| ~~~^~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |