PROBLEM LINK:
Author: chirag_mathur
Tester: hellb0y_suru
Editorialist: chirag_mathur
DIFFICULTY:
EASY
PROBLEM:
Given slots of Amit and Saurav
Saurav should shift his schedule by X which should be between L to R (inclusive) so that both can have the maximum common time.
Prerequisites:
- A little amount of brain to be applied while solving or understanding the editorial
EXPLANATION:
It is a very simple question, just implement what is written in the question. Make a prefix array of the slot timings of Amit, then simply iterate the slots of Saurav for every value of X and check the common time for every value of X. Print X for which there is maximum common time.
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define loop(a, b, i) for (ll i = a; i < b; i++)
int main()
{
ll tc = 1;
cin >> tc;
while (tc--)
{
ll p, q, l, r;
cin >> p >> q >> l >> r;
vector<pair<ll, ll>> a(p), b(q);
ll root[2004] = {0};
loop(0, p, i)
{
cin >> a[i].first >> a[i].second;
root[a[i].first]++;
root[a[i].second + 1]--;
}
loop(1, 2004, i) root[i] += root[i - 1];
loop(1, 2004, i) root[i] += root[i - 1];
loop(0, q, i)
{
cin >> b[i].first >> b[i].second;
}
ll a2 = r - b[q - 1].second;
ll ansf = 0, anst = 0;
ll ind = l;
loop(l, r + 1, i)
{
anst = 0;
loop(0, q, j)
{
if (b[j].first + i - 1 >= 0)
anst += root[b[j].second + i] - root[b[j].first + i - 1];
else
anst += root[b[j].second + i];
}
if (ansf < anst)
{
ansf = max(ansf, anst);
ind = i;
}
}
cout << ind << "\n";
}
return 0;
}
Tester's Solution
#include "bits/stdc++.h"
#define ll long long int
#define MOD 1000000007
#define oo 1000000000000000000
#define forr(i,n) for(int i=0;i<n;i++)
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define all(x) x.begin(),x.end()
#define eb emplace_back
#define FF first
#define SS second
#define mem(a,v) memset(a,v,sizeof(a))
#define pb push_back
using namespace std;
void __sol(){
int p,q,l,r; cin >> p >> q >> l >>r;
int a1[1010] , a2[1010];
mem(a1,0);
mem(a2,0);
forr(i,p){
int l,r; cin >> l >> r;
a1[l]++;
a1[r+1]--;
}
for(int i=1;i<=1000;i++) a1[i]+=a1[i-1];
forr(i,q){
int l,r; cin >> l >> r;
a2[l]++;
a2[r+1]--;
}
for(int i=1;i<=1000;i++) a2[i]+=a2[i-1];
int max_time = -1 , x = 0;
for(int i=l;i<=r;i++){
int cnt = 0;
for(int t=0;t<=1000;t++){
if( t-i>=0 && a1[t]>0 && a2[t-i]>0 ) cnt++;
}
if(cnt > max_time){
max_time = cnt;
x = i;
}
}
cout << x <<"\n";
return;
}
int main(){
fastio;
int tc=1; cin >> tc;
while(tc--) __sol();
return 0;
}