codechef ZCI 12002 - Wormholes
Solution in C++
#include <bits/stdc++.h>
using namespace std;
//Hello World
typedef long long int lli;
typedef long double ld;
#define pii pair<int,int>
#define pllilli pair<lli,lli>
#define piiti pair< pair<int,int>,int>
#define ipii pair<int,pair<int,int> >
#define mod 1000000007
#define lasB(b) (b&(-b))
#define N 4003
int n , x, y, t1 , t2 , sol=1e7;
vector<pii> all;
vector<int> V , W;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie();
cin>>n>>x>>y;
for(int i=0;i<n;i++)
{
cin>>t1>>t2;
all.push_back({t1,t2});
}
for(int i=0;i<x&&cin>>t1;i++)
V.push_back(t1);
for(int i=0;i<y&&cin>>t2;i++)
W.push_back(t2);
sort(V.begin(), V.end());
sort(W.begin(), W.end());
for(auto u : all)
{
int lb =upper_bound(V.begin(),V.end(), u.first)-V.begin();
int ub =upper_bound(W.begin(),W.end(), u.second)-W.begin();
if(u.second>W[y-1])
continue;
if(ub>0 && W[ub-1]>=u.second)
ub--;
int be= -1;
for(int i=lb-1;i>=0;i--)
{
if(V[i]<=u.first)
{
be=V[i];
break;
}
}
if(be!=-1)
sol=min(sol , W[ub]-be+1);
}
cout<<sol;
return 0;
}
0 التعليقات:
إرسال تعليق