In the problem QSET in jan15 long, I used segment trees and still TLE. Please explain.

general
, , ,
1

The code is pretty self-explanatory. I have closely followed the editorial. Can someone explain to me how to make this program faster? I’m guessing faster I/O is the key here. Is that so?

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#define ll long long
using namespace std;

struct stnode
{
	ll ans; // the answer for this interval
	ll pre[3]; // pre[i] denotes number of prefixes of interval which modulo 3 give i
	ll suf[3]; // suf[i] denotes number of suffixes of interval which modulo 3 give i
	ll total; // sum of interval modulo 3

	void setLeaf(int value)
	{
		if (value % 3 == 0) ans = 1;
		else ans = 0;
		pre[0] = pre[1] = pre[2] = 0;
		suf[0] = suf[1] = suf[2] = 0;
		pre[value % 3] = 1;
		suf[value % 3] = 1;
		total = value % 3;
	}

	void merge(stnode leftChild, stnode rightChild)
	{
		ans = leftChild.ans + rightChild.ans;
		for (int i = 0; i < 3; i++)
			for (int j = 0; j < 3; j++)
				if ((i + j) % 3 == 0) ans += leftChild.suf[i] * rightChild.pre[j];

		pre[0] = pre[1] = pre[2] = 0;
		suf[0] = suf[1] = suf[2] = 0;
		for (int i = 0; i < 3; i++)
		{
			pre[i] += leftChild.pre[i] + rightChild.pre[(3 - leftChild.total + i) % 3];
			suf[i] += rightChild.suf[i] + leftChild.suf[(3 - rightChild.total + i) % 3];
		}

		total = (leftChild.total + rightChild.total) % 3;
	}

	//void print()
	//{
	//	cout << ans << endl;
	//	for (auto i : pre) cout << i << " ";
	//	cout << endl;
	//	for (auto i : suf) cout << i << " ";
	//	cout << endl;
	//	cout << total << endl;
	//}
} segtree[400005];

void buildST(string digits, int si, int ss, int se)
{
	if (ss == se)
	{
		segtree[si].setLeaf(digits[ss] - '0');
		return;
	}
	long left = 2 * si + 1, right = 2 * si + 2, mid = (ss + se) / 2;
	buildST(digits, left, ss, mid);
	buildST(digits, right, mid + 1, se);
	segtree[si].merge(segtree, segtree[right]);
}

stnode getValue(int qs, int qe, int si, int ss, int se)
{
	if (qs == ss && se == qe)
		return segtree[si];

	stnode temp;
	int mid = (ss + se) / 2;
	if (qs > mid)
		temp = getValue(qs, qe, 2 * si + 2, mid + 1, se);
	else if (qe <= mid)
		temp = getValue(qs, qe, 2 * si + 1, ss, mid);
	else
	{
		stnode temp1, temp2;
		temp1 = getValue(qs, mid, 2 * si + 1, ss, mid);
		temp2 = getValue(mid + 1, qe, 2 * si + 2, mid + 1, se);
		temp.merge(temp1, temp2);
	}
	return temp;
}

void updateTree(int si, int ss, int se, int index, ll new_value)
{
	if (ss == se)
	{
		segtree[si].setLeaf(new_value);
		return;
	}

	int mid = (ss + se) / 2;
	if (index <= mid)
		updateTree(2 * si + 1, ss, mid, index, new_value);
	else
		updateTree(2 * si + 2, mid + 1, se, index, new_value);

	segtree[si].merge(segtree[2 * si + 1], segtree[2 * si + 2]);
}

int main()
{
	ios::sync_with_stdio(false);
	int n, m; cin >> n >> m;
	string digits; cin >> digits;
	buildST(digits, 0, 0, n - 1);
	while (m--)
	{
		int q; cin >> q;
		if (q == 1)
		{
			int x; int y; cin >> x >> y;
			updateTree(0, 0, n - 1, x - 1, y);
		}
		else
		{
			int c, d; cin >> c >> d;
			cout << getValue(c-1, d-1, 0, 0, n - 1).ans << '\n';
		}
	}
}
2

Yes fast i/o might be the key here…

3

cin/cout takes more time as compared to other kinds of i/o…so try out with scanf/printf also

4

Yeah same thing happened for me. just use fast i/o thats it…by the way why dint you try submitting it with fast i/o during the contest??

5

I found out what was making this program slow. The issue is not fast i/o. Using cin/cout with ios::sync_with_stdio(false) is fine.

In the buildST function, I pass the string digits. Since the function is recursive, and the input is fairly large, this creates many copies of the string digits thus incurring large overhead.

I declared a char digits[] at the start of the program and modified the method buildST as follows (basically same but without string digits as a parameter:

void buildST(int si, int ss, int se)
{
    if (ss == se)
    {
        segtree[si].setLeaf(digits[ss] - '0');
        return;
    }
    long left = 2 * si + 1, right = 2 * si + 2, mid = (ss + se) / 2;
    buildST(left, ss, mid);
    buildST(right, mid + 1, se);
    segtree[si].merge(segtree, segtree[right]);
}

This solution got accepted.

1 Like