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;
const int NStu = (int)1e5 + 5, NQue = NStu;
int nStu, nQue, ans[NQue];
vector<int> compMath, compInfo;
struct Stu {
int math, info;
Stu(int _math = 0, int _info = 0) : math(_math), info(_info) {}
bool operator<(const Stu &_) const { return math + info < _.math + _.info; }
} stu[NStu];
struct Que {
int a, b, c, initId;
Que(int _a = 0, int _b = 0, int _c = 0, int _initId = 0) : a(_a), b(_b), c(_c), initId(_initId) {}
bool operator<(const Que &_) const { return c < _.c; }
} que[NQue];
struct Bit2D {
vector<int> infoCnt[NStu];
vector<int> compInfo[NStu];
void updCompInfo(int math, int info) {
int x = (int)(lower_bound(compMath.begin(), compMath.end(), math) - compMath.begin() ) + 1;
for (; x < NStu; x += x & -x) {
compInfo[x].emplace_back(info);
}
}
void prep() {
for (int i = 1; i < NStu; ++i) {
sort(compInfo[i].begin(), compInfo[i].end() );
compInfo[i].erase(unique(compInfo[i].begin(), compInfo[i].end() ), compInfo[i].end() );
infoCnt[i].assign( (int)compInfo[i].size() + 1, 0);
}
}
void upd(int math, int info, int val) {
int x = (int)(lower_bound(compMath.begin(), compMath.end(), math) - compMath.begin() ) + 1;
for (; x < NStu; x += x & -x) {
int y = (int)(lower_bound(compInfo[x].begin() , compInfo[x].end(), info) - compInfo[x].begin() ) + 1;
for (; y < (int)infoCnt[x].size(); y += y & -y) infoCnt[x][y] += val;
}
}
int get(int math, int info) {
int ret = 0,
x = (int)(upper_bound(compMath.begin(), compMath.end(), math) - compMath.begin() );
for (; x > 0; x -= x & -x) {
int y = (int)(upper_bound(compInfo[x].begin() , compInfo[x].end(), info) - compInfo[x].begin() );
for (; y > 0; y -= y & -y) ret += infoCnt[x][y];
}
return ret;
}
} bit2D;
int main() {
// freopen("input", "r", stdin);
scanf(" %d %d", &nStu, &nQue);
for (int i = 1; i <= nStu; ++i) {
scanf(" %d %d", &stu[i].math, &stu[i].info);
stu[i].math = -stu[i].math; compMath.emplace_back(stu[i].math);
stu[i].info = -stu[i].info;
}
sort(stu + 1, stu + nStu + 1);
for (int i = 1; i <= nQue; ++i) {
scanf(" %d %d %d", &que[i].a, &que[i].b, &que[i].c);
que[i].a = -que[i].a;
que[i].b = -que[i].b;
que[i].c = -que[i].c;
que[i].initId = i;
}
sort(que + 1, que + nQue + 1);
sort(compMath.begin(), compMath.end() );
compMath.erase(unique(compMath.begin(), compMath.end() ), compMath.end() );
for (int i = 1; i <= nStu; ++i) {
bit2D.updCompInfo(stu[i].math, stu[i].info);
}
bit2D.prep();
int iStu = 1;
for (int i = 1; i <= nQue; ++i) {
while (iStu <= nStu && stu[iStu].math + stu[iStu].info <= que[i].c) {
bit2D.upd(stu[iStu].math, stu[iStu].info, 1);
++iStu;
}
ans[ que[i].initId ] = bit2D.get(que[i].a, que[i].b);
}
for (int i = 1; i <= nQue; ++i) printf("%d\n", ans[i]);
return 0;
}
Compilation message (stderr)
examination.cpp: In function 'int main()':
examination.cpp:59:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %d %d", &nStu, &nQue);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:62:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %d %d", &stu[i].math, &stu[i].info);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:69:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %d %d %d", &que[i].a, &que[i].b, &que[i].c);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# | 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... |