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>
using namespace std;
#define fi first
#define se second
#pragma GCC optimize("O3")
const int N = 3e5 + 5;
long long n,w,h,q,x[N],y[N],z[N],ans[N],cnt;
pair<long long,long long> stu[N];
pair<pair<int,int>,long long> com[N];
map<long long,int> idx,idy;
vector<long long> dmx,dmy,pos[N],node1[4*N];
vector<int> fen[4*N],point[N],query[N];
vector<pair<long long,int> > node[4*N];
//compress
void build1(int id,int l,int r,int i,int vt){
if(l>i || r<i){
return;
}
if(l == r){
node[id].push_back({com[vt].se, vt});
node1[id].push_back(com[vt].se);
return;
}
int mid = (l + r) >> 1;
build1(id<<1, l, mid, i, vt);
build1(id<<1|1, mid+1, r, i, vt);
node[id].push_back({com[vt].se, vt});
node1[id].push_back(com[vt].se);
}
void build(int id,int l,int r){
if(l == r){
sort(node[id].begin(), node[id].end());
sort(node1[id].begin(), node1[id].end());
for(int i = 0; i < node[id].size(); i++){
pos[node[id][i].se].push_back(i + 1);
}
fen[id].assign(node[id].size() + 5, 0);
return;
}
int mid = (l + r) >> 1;
build(id<<1, l, mid);
build(id<<1|1, mid+1, r);
sort(node[id].begin(), node[id].end());
sort(node1[id].begin(), node1[id].end());
for(int i = 0; i < node[id].size(); i++){
pos[node[id][i].se].push_back(i + 1);
}
fen[id].assign(node[id].size() + 5, 0);
}
//upd BIT
void upd(int id,int val,int index){
for(int i = id; i <= node[index].size(); i += (i&-i)){
fen[index][i] += val;
}
}
int get_sum(int id,int index){
int sum = 0;
for(int i = id; i >= 1; i -= (i&-i)){
sum += fen[index][i];
}
return sum;
}
//sweep update
void update(int id,int l,int r,int i,int vt){
if(l>i || r<i){
return;
}
if(l == r){
cnt++;
upd(pos[vt][cnt], 1, id);
return;
}
int mid = (l + r) >> 1;
update(id<<1, l, mid, i, vt);
update(id<<1|1, mid+1, r, i, vt);
cnt++;
upd(pos[vt][cnt], 1, id);
}
//ans query
int get(int id,int l,int r,int i,int j,long long val){
if(l>j || r<i || i>j){
return 0;
}
if(l>=i && r<=j){
if(node1[id].size() == 0 || node1[id][node1[id].size()-1] < val){
return 0;
}else{
int dm1 = lower_bound(node1[id].begin(), node1[id].end(), val) - node1[id].begin();
return get_sum(node1[id].size(), id) - get_sum(dm1, id);
}
}
int mid = (l + r) >> 1;
return get(id<<1, l, mid, i, j, val) + get(id<<1|1, mid+1, r, i, j, val);
}
//main
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> q;
for(int i=1;i<=n;i++){
cin >> stu[i].fi >> stu[i].se;
if(idx[stu[i].fi] == 0){
idx[stu[i].fi] = 1;
dmx.push_back(stu[i].fi);
}
if(idy[stu[i].se] == 0){
idy[stu[i].se] = 1;
dmy.push_back(stu[i].se);
}
}
for(int i=1;i<=q;i++){
cin >> x[i] >> y[i] >> z[i];
if(idx[x[i]] == 0){
idx[x[i]] = 1;
dmx.push_back(x[i]);
}
if(idy[y[i]] == 0){
idy[y[i]] = 1;
dmy.push_back(y[i]);
}
}
sort(dmx.begin(), dmx.end());
sort(dmy.begin(), dmy.end());
w = dmx.size(); h = dmy.size();
for(int i=0;i<dmx.size();i++){
idx[dmx[i]] = i+1;
}
for(int i=0;i<dmy.size();i++){
idy[dmy[i]] = i+1;
}
for(int i=1;i<=n;i++){
com[i].fi.fi = idx[stu[i].fi];
com[i].fi.se = idy[stu[i].se];
com[i].se = stu[i].fi + stu[i].se;
}
for(int i=1;i<=q;i++){
x[i] = idx[x[i]];
y[i] = idy[y[i]];
query[x[i]].push_back(i);
}
sort(com+1, com+1+n);
for(int i=1;i<=n;i++){
build1(1, 1, h, com[i].fi.se, i);
point[com[i].fi.fi].push_back(i);
}
build(1, 1, h);
for(int i = w; i >= 1; i--){
for(int j: point[i]){
cnt = -1;
update(1, 1, h, com[j].fi.se, j);
}
for(int j: query[i]){
ans[j] = get(1, 1, h, y[j], h, z[j]);
}
}
for(int i=1;i<=q;i++){
cout << ans[i] << "\n";
}
}
Compilation message (stderr)
examination.cpp: In function 'void build(int, int, int)':
examination.cpp:35:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < node[id].size(); i++){
~~^~~~~~~~~~~~~~~~~
examination.cpp:46:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < node[id].size(); i++){
~~^~~~~~~~~~~~~~~~~
examination.cpp: In function 'void upd(int, int, int)':
examination.cpp:54:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = id; i <= node[index].size(); i += (i&-i)){
~~^~~~~~~~~~~~~~~~~~~~~
examination.cpp: In function 'int main()':
examination.cpp:129:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<dmx.size();i++){
~^~~~~~~~~~~
examination.cpp:132:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<dmy.size();i++){
~^~~~~~~~~~~
# | 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... |