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 int long long
#define fr first
#define sc second
#define eb emplace_back
#define nl "\n"
struct BIT { // fenwick tree
int n;
vector<int> a;
BIT(int N) {
n = N - 1;
a.resize(N, 0);
}
void mod(int x, int v) {
while(x <= n) {
a[x] += v;
x += x&-x;
}
}
int qry(int x) {
int v = 0;
while(x >= 1) {
v += a[x];
x -= x&-x;
}
return v;
}
int qry(int x, int y) {
return qry(y) - qry(x - 1);
}
};
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, m;
cin >> n >> m;
pair<int, int> s[n + 1];
for(int i = 1; i <= n; ++i) {
cin >> s[i].fr >> s[i].sc;
}
pair<pair<int, int>, int> q[m];
for(int i = 0; i < m; ++i) {
cin >> q[i].fr.sc >> q[i].fr.fr;
int trash; cin >> trash;
q[i].sc = i;
}
sort(q, q + m);
reverse(q, q + m);
sort(s + 1, s + n + 1);
pair<int, int> t[n + 1];
for(int i = 1; i <= n; ++i)
t[i] = {s[i].sc, i};
sort(t + 1, t + n + 1);
reverse(t + 1, t + n + 1);
BIT bit(n + 1);
/* cout << "students\n"; */
/* for(int i = 1; i <=n; ++i) */
/* cout << s[i].fr << ' ' << s[i].sc << nl; */
/* cout << nl; */
/* cout << "secondary marks\n"; */
/* for(int i = 1; i <= n; ++i) */
/* cout << t[i].fr << ' ' << t[i].sc << nl; */
/* cout << nl; */
/* cout << "queries\n"; */
int ans[m];
int j = 0;
for(auto u : q) {
int y = u.fr.fr, x = u.fr.sc, idx = u.sc;
/* cout << x << ' ' << y << nl; */
while(j + 1 <= n && t[j + 1].fr >= y) {
bit.mod(t[++j].sc, 1);
}
/* for(int i = 1; i<=n; ++i) */
/* cout << bit.qry(i, i) << ' '; */
/* cout << nl << nl; */
ans[idx] = bit.qry(x, n);
}
for(auto u : ans)
cout << u << ' ';
}
# | 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... |