HELP IN KQUERY TLE with merge sort segment tree + upperbound

[hraj123]

#include <bits/stdc++.h>
#define int long long

using namespace std;

vector a;
vector<vector> seg;
int n, m;
// Root node covers the range [0,n-1] or [0,n)

vector create(int num) {
vector temp;
temp.push_back(num);
return temp;
}

vector combine(const vector& a, const vector& b) {
int m = a.size(), n = b.size();
int i = 0, j = 0;
vector c;

while (i < m && j < n) {
if (a[i] <= b[j]) {
c.push_back(a[i]);
i++;
} else {
c.push_back(b[j]);
j++;
}
}

while (i < m) {
c.push_back(a[i]);
i++;
}

while (j < n) {
c.push_back(b[j]);
j++;
}
return c;
}

// Range is [l,r-1] or [l,r)
void build(int id = 1, int l = 0, int r = n) {
if (r - l == 1) {
seg[id] = create(a[l]);
return;
}
int mid = (l + r) / 2;
build(id * 2, l, mid);
build(id * 2 + 1, mid, r);
seg[id] = combine(seg[id * 2], seg[id * 2 + 1]);
}
// Time complexity: O(n*log(n))

// x : no. of rooms
int query(int x, int y, int k, int id = 1, int l = 0, int r = n) {
if (r <= x || l >= y) return 0;
if (l >= x && r <= y) {
int ans =
(int)seg[id].size() -
(upper_bound(seg[id].begin(), seg[id].end(), k) - seg[id].begin());
return ans;
}
int mid = (l + r) / 2;
int l_ans = query(x, y, k, id * 2, l, mid);
int r_ans = query(x, y, k, id * 2 + 1, mid, r);
return l_ans + r_ans;
}
// Time complexity: O( log^2(N) )

int32_t main() {

cin >> n;

a.resize(n);
seg.resize(4 * n + 1);

for (int i = 0; i < n; i++) {
cin >> a[i];
}

build();
cin >> m;

while (m–) {
int i, j, k;
cin >> i >> j >> k;
i–;
int ans = query(i, j, k);
cout << ans << ‘\n’;
}

return 0;
}

[simes]

#ifndef ONLINE_JUDvE

Does it really say that in your submitted code?

[hraj123]

no, edited

[tjm]

A few suggestion (the first one is probably the one responsible for TLE):

• By default std::cin is tied to std::cout. This means that before each operation on std::cin the std::cout stream is flushed. You can disable this with std::cin.tie(nullptr);.
• When iostream is the only method of I/O, you can disable synchronization with stdio for slight speedup: std::ios_base::sync_with_stdio(false);.
• In combine the size of resulting vector is known. Use c.reserve(...) to preallocate required space and avoid intermediate reallocations.
• The input fits in 32-bit integer type (remove #define int long long to reduce memory usage).

[oniechan]

Hey anyone got the correct solution, if yes the please share
#include<stdio.h>
#include
#include
#include

using namespace std;
typedef long long int ll;
// #define int ll
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define mp make_pair
#define pb push_back
#define llM LONG_LONG_MAX
#define llm LONG_LONG_MIN
#define all(x) (x).begin(), (x).end()
#define endl “\n”
#define file freopen(“input.txt”, “r”, stdin), freopen(“output.txt”, “w”, stdout)

template
ostream& operator<<(ostream& COUT, vector& v){ for(int i=0 ; i<v.size() ; i++){ COUT<<v[i]<<" “; } COUT << endl; return COUT; }
template
ostream& operator<<(ostream& COUT, pair<T, T>& p){ cout << p.first <<” "<< p.second <<endl; return COUT; }
template
istream& operator>>(istream& CIN, vector& a){ for(int i=0 ; i<a.size() ; i++) CIN>>a[i]; return CIN; }
template
istream& operator>>(istream& CIN, pair<T, T>& p){ cin >> p.first >> p.second ; return CIN; }
template
T max(vector& v){ T m=v[0]; for(auto e : v){ m = max(m, e); } return m; }
template
T min(vector& v){ T m=v[0]; for(auto e : v){ m = min(m, e); } return m; }

ll mod = 1000000007;

vector tree[4*30000];

void build(int n, int l, int r, vector& a){
if(l==r) tree[n] = vector(1, a[l]);
else{
int m = (l+r)/2;
build(2n, l, m, a);
build(2n+1, m+1, r, a);
merge(tree[2n].begin(), tree[2n].end(), tree[2n+1].begin(), tree[2n+1].end(), back_inserter(tree[n]));

}

}

int query(int n, int l, int r, int ql, int qr, int k){
// cout<<ql<<" "<<qr<<endl;
if(ql>qr) return 0;
if(ql==l && qr==r){
return tree[n].end() - upper_bound(tree[n].begin(), tree[n].end(), k);
}
else{
int m = (l+r)/2;
return query(2n, l, m, ql, min(qr, m), k) +
query(2n+1, m+1, r, max(ql, m+1), qr, k);
}
}

void solve(){
int n;
cin >> n;
vector a(n);
cin >> a;
build(1, 0, n-1, a);
// cout << “done<”<<endl;
int q;
cin >> q;
while(q–){
int i, j, k;
cin >> i >> j >> k;
cout << query(1, 0, n-1, i-1, j-1, k) <<endl;
}
}

signed main()
{
//IOS
//file;
int T=1;
// cin >> T;
for (int i = 0; i < T; ++i){
// cout<<“Case #”<<i+1<<": ";
solve();
}

}
I am still getting TLE, please share some solution so that I can at least analyze/

[simes]

I see you’ve now got AC. Did you solve your problem, or was that with a shared solution?

edit: oh now I realise you’re not the OP, but have hijacked the thread.

[hraj123]

Thanks, it got AC

[hraj123]

Got AC with this code using fast I/O

[nik4o]

I think this can help you: https://codeforces.com/blog/entry/15890
View section “classic segment tree”.