hustler_72's blog

By hustler_72, history, 3 years ago, In English

Hello, everyone! I was learning Segment Tree and was trying problems on CSES. I came across the following problem — CSES — Task — 1647.

Problem Statement
Given an array of $$$n$$$ integers, your task is to process $$$q$$$ queries of the form: what is the minimum value in range $$$[a,b]$$$?

INPUT
The first input line has two integers $$$n$$$ and $$$q$$$: the number of values and queries.
The second line has $$$n$$$ integers $$$x_1,x_2,\dots,x_n$$$: the array values.
Finally, there are $$$q$$$ lines describing the queries. Each line has two integers $$$a$$$ and $$$b$$$. What is the minimum value in range $$$[a,b]$$$?

OUTPUT
Print the result of each query.

Constraints
$$$1 \le n,q \le 2 \cdot 10^5$$$
$$$1 \le x_i \le 10^9$$$
$$$1 \le a \le b \le n$$$

Following is my submission to this problem

// ====================================
// Template by Taukirahmed Khatri
// ====================================
 
#include "bits/stdc++.h"
using namespace std;
 
#define fast_io                   \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0)
 
typedef long long ll;
#define vi vector<ll>
#define pb push_back
 
#define nl "\n"
#define print(a)          \
    for (auto &i : a)     \
        cout << i << " "; \
    cout << nl
#define yesno(x) cout << (((x)) ? "YES" : "NO") << nl
#define cntdig(x) floor(log(x) + 1)
 
#define fra(i, init, n, inc) for (i = init; i < n; i += inc)
#define frd(i, init, n, dec) for (i = init; i >= n; i -= dec)
 
bool sortbysec(pair<int, int> &a, pair<int, int> &b)
{
    return a.second < b.second;
}
 
void tv(vi &a, ll n)
{
    ll i = 0;
    fra(i, 0, n, 1)
    {
        ll t;
        cin >> t;
        a.pb(t);
    }
}
 
class segment_tree
{
    vector<ll> sg;
    ll n;
 
public:
    segment_tree(ll dn)
    {
        n = dn;
        sg.resize(4 * n);
    }
 
    void build(vector<ll> a, ll start, ll end, ll cur_node)
    {
        if (start == end)
        {
            sg[cur_node] = a[start];
            return;
        }
        ll mid = (start + end) / 2;
        build(a, start, mid, 2 * cur_node);
        build(a, mid + 1, end, 2 * cur_node + 1);
        sg[cur_node] = min(sg[2 * cur_node], sg[2 * cur_node + 1]);
    }
 
    ll query(ll start, ll end, ll cur_node, ll left, ll right)
    {
        if (end < left || start > right)
            return LONG_MAX;
 
        if (start >= left && end <= right)
            return sg[cur_node];
 
        ll mid = (start + end) / 2;
        ll lres = query(start, mid, 2 * cur_node, left, right);
        ll rres = query(mid + 1, end, 2 * cur_node + 1, left, right);
        return min(lres, rres);
    }
};
 
void my_sol()
{
    ll n, q;
    cin >> n >> q;
    vi a;
    tv(a, n);
    segment_tree s(n);
    s.build(a, 0, n - 1, 1);
    vi ans;
    for (ll i = 0; i < q; i++)
    {
        ll l, r;
        cin >> l >> r;
        ans.push_back(s.query(0, n - 1, 1, l - 1, r - 1));
    }
    for (auto i : ans)
        cout << i << endl;
}
 
int main()
{
    fast_io;
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    auto start = std::chrono::high_resolution_clock::now();
#endif
 
    // ll t;
    // cin >> t;
    // while (t--)
    my_sol();
 
#ifndef ONLINE_JUDGE
    auto stop = std::chrono::high_resolution_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::microseconds>(stop - start);
    long double t1 = (long double)duration.count() / 1000000;
    cout << "\n\nTime taken " << fixed << setprecision(6) << t1 << " seconds ";
#endif
    return 0;
}
I don't know why it is giving TLE. Any idea? I was searching for a better solution. But sadly I failed. Hope from here, I will get some hints. Thank you :)
  • Vote: I like it
  • +5
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

try "\n" instead of endl since endl is slower

»
3 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Arguments should be passed by reference. In the build function do this.

    void build(vector<ll> &a, ll start, ll end, ll cur_node)

Same code with above change