HackerEarth A special sequence problem solution

In this HackerEarth A special sequence problem solution An array A contains integers with the following constraints:

A contains elements in sorted order.
Integer i occurs i x floor(sqrt(i)) + ceil(i/2) times in the array.
All elements are greater than or equal to 1.

You are given Q queries of type:

L R: Find the number of distinct values present in subarray A[L…R].

HackerEarth A special sequence problem solution.

#include<bits/stdc++.h>
#define ll long double
using namespace std;
vector<long long>p;

signed main(){
    long long sum = 0;
    p.push_back(0);
    for(ll i = 1 ; i <= 500000 ; i++){
        long long val = i*floor(sqrt(i)) + ceil(i/2);
        p.push_back(val);
    }

    int sz = p.size();

    for(int i = 1 ; i < sz ; i++){
        p[i] += p[i-1];
    }

    int q;
    cin >> q;
    assert(1 <= q and q <= 100000);
    while(q--){
        long long l, r;
        cin >> l >> r;
        assert(1 <= l and l <= r and r <= 10000000000000);
        int s = 0;
        int e = sz - 1;
        int ans1 = -1;
        while(s <= e){
            int m = (s + e)/2;
            if(p[m] < l){
                ans1 = m;
                s = m + 1;
            }
            else{
                e = m - 1;
            }
        }

        ans1++;

        s = 0;
        e = sz - 1;
        int ans2 = -1;
        while(s <= e){
            int m = (s + e)/2;
            if(p[m] < r){
                ans2 = m;
                s = m + 1;
            }
            else{
                e = m - 1;
            }
        }
        ans2++;

        cout << (ans2 - ans1 + 1) << endl;
    }   
}

Second solution

from bisect import bisect_left
from math import sqrt

import os
import sys
from io import BytesIO, IOBase

_str = str
str = lambda x=b"": x if type(x) is bytes else _str(x).encode()

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


input = lambda: sys.stdin.readline().rstrip("rn")


a = [2]
while a[-1] < 1e13:
    i = len(a) + 1
    a += [a[-1] + i * int(sqrt(i)) + (i + 1) // 2]
q = int(input())
while q > 0:
    q -= 1
    l, r = map(int, input().split())
    print(bisect_left(a, r) - bisect_left(a, l) + 1)

coding problems