Need Help With a Segment Tree Problem (Knight Tournament)

general
1

I am solving a problem named Knight Tournament. My approach is based upon segment trees.

I think my update function and overall code works in logarithmic time

However i’m getting time limit exceeded.

Can someone point out where i’m going wrong in terms of complexity
(because i think i’m doing updates in O(log(n)) ) )

Before i show my code, i would like to add that, I’m already using Fast IO, and no it doesn’t work. I’ve tried #pragma optimizations too… and that too didn’t help much

Here is my code, help is appreciated

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=100005;

int tree[4*N+1];
int num[N];

int numtotree[N];
void update(int idx,int s,int e,int l,int r,int val){
	if(r<s||l>e)return;
	if(s==e){
		if(tree[idx]==0)
			tree[idx]=val;
		
		numtotree[s]=idx;
		return;
	}
	int m=(s+e)/2;
	update(2*idx,s,m,l,r,val);
	update(2*idx+1,m+1,e,l,r,val);
	tree[idx]=val;
	return;
}


void display(int n){
	for(int i = 0; i < n ; i ++){
		cout << tree[numtotree[i]] << ' ';
	}
	cout<<endl;
}


int32_t main(){
	ios_base::sync_with_stdio(false);cin.tie(0);	
	int n , m ;
	cin >> n >> m;

	while(m--){
		int l , r , x;
		cin >> l >> r >> x;
		update(1,0,n-1,l-1,r-1,x);
		tree[numtotree[x-1]]=0;
	
	}
	display(n);
}
2

I don’t think that your update function is logarithmic. It is basically just going to each element and updating its value in log N. Individually for every element its log N but in total for a range it will TLE.
In a basic Segment Tree, we only update one value so that’s fine, but here you are trying to update a range, that will be a problem.

I suggest you to just simulate the process as stated in the statement.

#include <bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

vi P(3*MAX);

int main()
{	
	fastio
	int n,m;
	cin>>n>>m;
	set<int> S;
	for(int i=1;i<=n;i++) S.insert(i);
	while(m--)
	{
		int l,r,x;
		cin>>l>>r>>x;
		auto y=S.lower_bound(l);
		vector<int> toerase;
		while(y!=S.end())
		{
			if(*y>r) break;
			if(*y!=x)
			{
				P[*y]=x;
				toerase.push_back(*y);
			}
			y++;
		}
		for(auto xx:toerase) S.erase(xx);
	}
	for(int i=1;i<=n;i++) cout<<P[i]<<" ";
	cout<<endl;
}

Keep a set of currently active Knights and in each round, remove every Knight in the set between the given range, while updating their parent as the winner of the round. Since atmost there will be N deletions, the time complexity is O(NlogN).

3

this code works check this