Problem
I can solve this using binary search. Is it possible to solve it using PBDS?
Yeah its possible, here’s my solution
AC_CODE
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define FOR(i,n) for(int i=0;i<n;i++)
template<class T> using oset =tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update> ;
int n,q,x,l,r;
oset<int>s;
int qry(int x){
return s.order_of_key(x);
}
signed main() {
cin >> n >> q ;
FOR(i,n)
cin >> x,s.insert(x);
while(q--)
cin >> l>>r ,cout << qry(r+1)-qry(l)<< "\n";
}
3 Likes
Thanks!
It is so simple with PBDS.
1 Like
c:\mingw\lib\gcc\mingw32\9.2.0\include\c++\ext\pb_ds\hash_policy.hpp|610|fatal error: ext/pb_ds/detail/resize_policy/hash_standard_resize_policy_imp.hpp: No such file or directory|
I get this error when I run my code. The same happens with yours.
My code:
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
template <class T> using oset = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
oset <int> s;
int n, q, x, l, r;
cin >> n >> q;
for (int i = 0; i < n; ++i)
{
cin >> x;
s.insert(x);
}
while (q--)
{
cin >> l >> r;
cout << s.order_of_key(r+1)-s.order_of_key(l) << '\n';
}
}
What g++version do you have ?
9.2
btw if you only want to test your code then you can test it on codechef’s online ide it works fine there
Thanks!
I had to remove 0000644
from hash_standard_resize_policy_imp.hpp0000644
.