6 / 6
Dec 2022
#include<bits/stdc++.h>
using namespace std;
// #include "atcoder/math.hpp"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define endl "\n"
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define mp make_pair
#define fi first
#define se second
#define set_bits __builtin_popcountll
#define precise(ans)  cout<<fixed<<setprecision(15)<<ans
#define fo(i,n) for(ll i=0;i<n;i++)
#define Fo(i,k,n) for(ll i=k;k<n?i<n:i>n;k<n?i+=1:i-=1)
#define tr(it, a) for(auto it = a.begin(); it != a.end(); it++)
#define sz(x) ((ll)(x).size())
#define all(x) x.begin(), x.end()
#define sortall(x) sort(all(x))
#define clr(x) memset(x, 0, sizeof(x))
typedef long long ll; typedef unsigned long long ull; typedef long double lld; typedef pair<ll, ll>  pii;
typedef pair<ll, ll>    pl; typedef vector<ll> vi; typedef vector<vi> vvi; typedef vector<vvi>    vvvi;
typedef vector<ll>  vl; typedef vector<vl>  vvl; typedef vector<pii> vpii; typedef vector<pl>  vpl;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>ordered_set;
#define PI 3.1415926535897932384626
#define MOD 1000000007
#define MOD1 998244353
const double eps = 1e-9; const ll INF = (ll) 1e9; const ll inf64 = 2e18; const ll INF64 = 9e18;
ll dx[4] = {0, 0, 1, -1}; ll dy[4] = {1, -1, 0, 0};
ll ddx[8] = { -1, 0, 0, 1, 1, -1, 1, -1}; ll ddy[8] = {0, 1, -1, 0, 1, -1, -1, 1};
const ll dddx[16] = {1, 0, 0, -1, 1, 1, -1, -1, 2, 2, 1, 1, -1, -1, -2, -2};
const ll dddy[16] = {0, -1, 1, 0, -1, 1, -1, 1, -1, 1, -2, 2, -2, 2, -1, 1};
#ifndef ONLINE_JUDGE
#define debug(x) cerr << #x <<" "; _prll(x); cerr << endl;
#else
#define debug(x)
#endif
void _prll(ll t) {cerr << t;} void _print(ll t) {cerr << t;} void _prll(string t) {cerr << t;} void _prll(char t) {cerr << t;}
void _prll(lld t) {cerr << t;} void _prll(double t) {cerr << t;} void _prll(ull t) {cerr << t;}
template <class T, class V> void _prll(pair <T, V> p); template <class T> void _prll(vector <T> v);
template <class T> void _prll(set <T> v);
template <class T, class V> void _prll(map <T, V> v); template <class T> void _prll(multiset <T> v);
template <class T, class V> void _prll(pair <T, V> p) {cerr << "{"; _prll(p.fi); cerr << ","; _prll(p.se); cerr << "}";}
template <class T> void _prll(vector <T> v) {cerr << "[ "; for (T i : v) {_prll(i); cerr << " ";} cerr << "]";}
template <class T> void _prll(set <T> v) {cerr << "[ "; for (T i : v) {_prll(i); cerr << " ";} cerr << "]";}
template <class T> void _prll(multiset <T> v) {cerr << "[ "; for (T i : v) {_prll(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _prll(map <T, V> v) {cerr << "[ "; for (auto i : v) {_prll(i); cerr << " ";} cerr << "]";}
vector<ll> factors(ll n) {vector<ll> f; while (n % 2 == 0) {f.push_back(2) ;    n = n / 2  ;} for (ll x = 3; x * x <= n; x += 2) {while (n % x == 0) {f.push_back(x); n /= x;}} if (n > 1) f.push_back(n); return f;}
ull power(ull x , ull y, ll p) {ull res = 1; while (y > 0) { if (y & 1) res = res % p * x % p; y = y >> 1;  x = x % p * x % p;  } return res;}
bool palindrome(const string &s) {ll n = s.length(); for (ll i = 0; i < n; i++) {if (s[i] != s[n - i - 1]) return false;} return true;}
ll inv(ll a, ll p) {return power(a, p - 2, p);}
ll nCk(ll n, ll k, ll p, vl fact) {return ((fact[n] * inv(fact[k], p) % p) * inv(fact[n - k], p)) % p;}
bool isPrime(ll n) {if (n <= 1) {return false;} for (ll i = 2; i < n; i++) {if (n % i == 0) {return false;}} return true;}
map<ll, ll> primeFactorize(ll x) {ll num = x; map<ll, ll> store; for (ll i = 2; i <= sqrt(x); i++) {ll cnt = 0; while ((num % i) == 0) {num /= i; cnt++;} if (cnt) store[i] = cnt;} if (num > 1) store[num]++; return store;}
vl initfact(ll n, ll p = pow(10, 9) + 7) {vector<ll> fac(n + 1); fac[0] = 1; for (ll i = 1; i <= n; i++) {fac[i] = (fac[i - 1] * i) % p;} return fac;}
// ll countSetBits(ll n) {ll count = 0; while (n) {count += n & 1; n >>= 1;} return count;}
ll int_sqrt (long long x) {long long ans = 0; for (ll k = 1LL << 30; k != 0; k /= 2) {if ((ans + k) * (ans + k) <= x) {ans += k;}} return ans;}
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
const ll MX= 1e5+100,MAXK=25;
vvl spt(MX,vl(MAXK+1));
vl aa(MX);
void buildST(ll n)
{
  for(ll i=0; i<n; i++)
{
    spt[i][0] = aa[i];
}
for(ll k=1; k <= MAXK ; k++)
{
  for(ll i=0; i+( 1LL<<k)<=n; i++)
  { 
       spt[i][k] = min(spt[i][k-1],spt[ i + (1LL<<(k-1)) ][k-1]); 
  }
}
}
ll minquery(ll l, ll r)
{
  if(l>r) return INT_MAX;
  ll j = (ll)log2(r - l + 1);
  // ll j = 31 - __builtin_clz(r - l+1);
  return min (spt[l][j], spt[r - (1 << j) + 1][j]);
}

void chal() {
  ll n;
  cin>>n;
  fo(i,n){
    cin>>aa[i];
  }
  buildST(n);
  ll q;
  cin>>q;
  while(q--){
    ll L,R;
    cin>>L>>R;
    cout<<minquery(L,R)<<endl;
 
  }
  

} 
int32_t main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  srand(chrono::high_resolution_clock::now().time_since_epoch().count());
#ifndef ONLINE_JUDGE
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
  freopen("Error.txt", "w", stderr);
#endif
  ll  t; t = 1;
  // cout << "Chal Raha Ho Ma";

  for (ll i = 1; i <= t; i++) {
    chal();
  }
  return 0;
}

problem : - https://www.spoj.com/problems/RMQSQ/5

ide one giving runtime error on running
fo(i,25){
cout<<(1LL<<i)<<endl;
}

in cpp but it run on other ide.

Edit:
Accepted in : CPP14-CLANG
but not in Cpp14(gcc8.) Compiler… Why?

  • created

    Dec '22
  • last reply

    Dec '22
  • 5

    replies

  • 868

    views

  • 2

    users

  • 1

    like

  • 1

    link

Not any C++ I recognise. What is your particular #define for it?

Please post code that I can compile without having to fix.

I have changed the code . (I was solving different problem so t variable remains in code.)

It’s something to do with these lines. Comment them out, and it no longer faults.

Edit: Also, it’s something to do with lines with this. I don’t understand how, but it’s been a long time since I’ve coded in C or C++ in earnest.

1LL<< k