Решение задачи "Антон и занятия" с Codeforces

Без пояснения   Просмотров: 11

Антону нравятся шахматы. А еще ему нравится программирование. Неудивительно, что он решил посещать занятия по шахматам и по программированию.

У Антона есть n вариантов, когда он будет заниматься шахматами, i-й вариант задается отрезком времени (l 1, i, r 1, i). Также у него есть m вариантов, когда он будет заниматься программированием, i-й вариант задается отрезком времени (l 2, i, r 2, i).

Антону необходимо выбрать ровно один из n возможных отрезков времени, когда он будет заниматься шахматами и ровно один из m возможных отрезков времени, когда он будет заниматься программированием. Ему хочется побольше отдохнуть между занятиями, поэтому из всех возможных пар отрезков он хочет выбрать ту, расстояние между отрезками в которой как можно больше.

Расстоянием между двумя отрезками (l 1, r 1) и (l 2, r 2) будем называть минимально возможное расстояние между точкой на первом отрезке и точкой на втором отрезке, то есть минимально возможное |i - j|, где l 1 ≤ i ≤ r 1 и l 2 ≤ j ≤ r 2. В частности, если отрезки пересекаются, то расстояние между ними равно 0.

Антону интересно, сколько времени он сможет отдохнуть между занятиями в лучшем случае. Помогите ему найти это число!

Код 

#include<bits/stdc++.h>
using namespace std;
int n,l,r,mn1=1e9,mn2=1e9,mx1,mx2;
int main()
{
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>l>>r;
		mn1=min(mn1,r);
		mx1=max(mx1,l);
	}
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>l>>r;
		mn2=min(mn2,r);
		mx2=max(mx2,l);
	}
	int ans=max(0,max(mx2-mn1,mx1-mn2));
	cout<<ans;
	return 0;
}

         

Администратор Photo Автор: Администратор


Отправить решение задачи
Чтобы отправить решение вам нужно войти в систему или зарегистрироваться

Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться