Counting Haybales - USACO Silver '16

1

Problem
I can solve this using binary search. Is it possible to solve it using PBDS?

2

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
3

Thanks!
It is so simple with PBDS.

1 Like
4

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';
    }
}
5

What g++version do you have ?

6

9.2

7

This should help I think

1 Like
8

btw if you only want to test your code then you can test it on codechef’s online ide it works fine there

9

Thanks!
I had to remove 0000644 from hash_standard_resize_policy_imp.hpp0000644.