#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include<bits/stdc++.h>
#include<math.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef pair<ll, ll> pl;
#define K first
#define V second
#define G(x) ll x; cin >> x;
#define GD(x) ld x; cin >> x;
#define GS(s) string s; cin >> s;
#define EX(x) { cout << x << '\n'; exit(0); }
#define A(a) (a).begin(), (a).end()
#define F(i, l, r) for (ll i = (l); i < r; ++i)
#define NN 100010
#define M 1000000007 // 998244353
//GCC extensions
#include <bits/extc++.h>
using namespace __gnu_cxx;
using namespace __gnu_pbds;
struct query_multiset {
// multiset that keeps track of things above you (basically oset)
map<ll, ll> cnts;
// order stats tree
// find_by_order(i) returns ptr
// order_of_key(key) return int
typedef tree<pl, null_type, less<pl>,
rb_tree_tag, tree_order_statistics_node_update> set_t;
set_t oset;
void insert(ll i) {
oset.insert(pl{i, ++cnts[i]});
}
// returns how many elements >= i
ll query(ll i) {
return oset.size() - oset.order_of_key(pl{i, -1});
}
};
namespace mstree {
query_multiset t[2 * NN];
vector<ll> items;
ll n;
ll f(ll i, ll k) {
cout << "Im querying " << k << ": " << t[i].query(k) << endl;
for (const auto &[k, v]: t[i].cnts) cout << k << ", " << v << endl;
return t[i].query(k);
}
void init() {
sort(A(items));
items.erase(unique(A(items)), items.end());
n = items.size();
}
void add(ll a, ll b) {
// A should always be in items
ll idx = lower_bound(A(items), a) - items.begin();
idx += n;
for (t[idx].insert(b); idx/=2;) t[idx].insert(b);
}
ll i_query(ll l, ll r, ll k) { //num elements < k in interval [l, r)
ll res = 0;
for(l += n, r += n; l < r; l /= 2, r /= 2) {
if(l & 1) res += f(l++, k);
if(r & 1) res += f(--r, k);
}
return res;
}
ll query(ll a, ll b) {
// a isn't necessarily guranteed to be in items
ll suff = ll(lower_bound(A(items), a) - items.begin());
// cout << "query " << a << " " << b << endl;
// for (auto x: items) cout << x << " " ; cout << endl;
// cout << suff << ", " << a << endl;
return i_query(suff, n, b);
}
}
int main(){
// freopen("a.in", "r", stdin);
// freopen("a.out", "w", stdout);
ios_base::sync_with_stdio(false); cin.tie(0);
cout << fixed << setprecision(20);
G(n) G(qn)
vector<pair<ll, array<ll, 3>>> q;
vector<pl> students;
F(i, 0, n) {
G(x) G(y) students.emplace_back(x, y); mstree::items.push_back(x);
}
mstree::init();
sort(A(students), [](const auto &a, const auto &b) {
return a.K + a.V > b.K + b.V;
});
F(i, 0, qn) {
array<ll, 3> arr; F(i, 0, 3) cin >> arr[i];
q.emplace_back(i, arr);
}
vector<ll> ans(qn);
sort(A(q), [](const auto &a, const auto &b) {
return a.V[2] > b.V[2];
});
ll fp = 0;
for (const auto &[qidx, qarr]: q) {
auto &[a, b, c] = qarr;
while (fp < n && students[fp].K + students[fp].V >= c) {
mstree::add(students[fp].K, students[fp].V);
fp++;
}
ans[qidx] = mstree::query(a, b);
}
for (auto x: ans) cout << x << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
28504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3052 ms |
256100 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3052 ms |
256100 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
28504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
