Question A of ICPC2021 first network qualifier

The meaning of question A is that there are n machines and m programs to be run. The input will give the number of machines, as well as the arrival time and running time of each program. Find the machine with the most processing programs and output them according to the subscript of the machine.
PS (when the ith program arrives, it will start looking for the first idle machine from the i%n machine, that is, it will look for the first idle machine from i%n - n. if there is no idle machine, it will look for it from 1 - (i%n - 1). If all machines are not idle, this program will be discarded)

Problem solving idea: from the meaning of the problem, we can analyze that each program is actually in i%n - n and 1 - (i%n - 1)
The first idle machine is found in the two intervals. When I see the interval query, I think of the segment tree. Then we consider what the segment tree can maintain and find out whether each machine can execute the current program. We only need to judge whether the idle time of the current machine is less than the arrival time of the current program. If we store the idle time of each machine in the segment tree node, then Then you can query whether there is an idle machine in any interval according to the complexity of log^n, and you can process the current program, because the problem means to find the first idle machine, which can be transformed into a problem of interval existence, so you can use dichotomy to find the interval existence to solve the first idle machine. Therefore, this problem can be solved by using segment tree + dichotomy , time complexity O(log2n * n). PS (field AC code forgot to save, this code is hand-held after the game, and AC is not guaranteed)

#include"iostream"
#include"algorithm"

using namespace std;
typedef long long ll;
const int N = 1e5 + 10;

struct node
{
	int l, r;
	ll val;
}tr[N * 4];
int cnt[N];
ll last[N];

void pushup(int u)
{
	tr[u].val = min(tr[u << 1].val, tr[u << 1 | 1].val);
}

void build(int u,int l,int r)
{
	if(l == r)tr[u] = {l, r};
	else
	{
		tr[u] = {l, r};
		int mid = l + r >> 1;
		build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r); 
	}
}

void update(int u,int x,ll c)
{
	if(tr[u].l == x && tr[u].r == x)tr[u].val = c;
	else
	{
		int mid = tr[u].l + tr[u].r >> 1;
		if(x <= mid)update(u << 1, x, c);
		else update(u << 1 | 1, x, c);
	}
}

ll query(int u,int l,int r)
{
	if(tr[u].l >= l && tr[u].r <= r)return tr[u].val;
	else
	{
		int mid = tr[u].l + tr[u].r >> 1;
		ll res = 1e18;
		if(mid >= l)res = query(u << 1, l, r);
		if(r > mid)res = min(res , query(u << 1 | 1, l, r));
		
		return res;
	}
}

int main()
{
	int n, m;
	cin >> n >> m;
	build(1 , 1, n);
	
	int id = 0;
	while(m --)
	{
		id ++;
		int x , y;
		scanf("%d %d", &x, &y);
		if(id > n)id -= n;
		
		int l = id, r = n;
		while(l < r)
		{
			int mid = l + r >> 1;
			if(query(1, l, mid) <= x)r = mid;
			else l = mid + 1;
		}
		
		if(last[l] <= x)
		{
			last[l] = x + y;
			cnt[l] ++;
			update(1, l, last[l]);
		}
		else
		{
			 l = 1, r = id - 1;
			if(r < l)continue;
			while(l < r)
			{
				int mid = l + 1 >> 1;
				if(query(1, l, mid) <= x)r = mid;
				else l = mid + 1;
			}
			
			 if(last[l] <= x)
	    	  {
		     	last[l] = x + y;
		     	cnt[l] ++;
		    	update(1, l, last[l]);
		      }
		}
	}
	
	int maxn = 0;
	for(int i = 1; i <= n ;i ++)
	maxn = max(maxn , cnt[i]);
	
	int ans[N], cns = 0;
	for(int i = 1; i <= n ;i ++)
	if(cnt[i] == maxn)ans[cns ++] = i;
	
	sort(ans, ans + cns);
	
	for(int i = 0; i < cns; i ++)
	cout << ans[i] << ' ';
}