Thank you sooo much.That is what happens most of the time I missed testcases 
or took tym to reach optimized one during contest.
No the time interval would have been x-b, written ad x-1-(b-1) to comply with the representation of the interval that was written earlier, which itself might have gotten confusing because both extremities inclusive was specified, it thus being different than the one used in the question. Thank you for bringing that to notice I have edited it to comply with the rest of the times intervals are used.
2 Likes
For test case:
2 2 100
99 100
2 3
The spare in your code must return 98, however it returns 2.
1 Like
s[i] and e[i] must be less than f it is already given in question.
Please Help .My code is given wrong answer . why??
#include<bits/stdc++.h>
#define fast ios_base::sync_with_stdio(false);cin.tie(0);
#define lli long long int
#define vi vector<lli>
#define vii vector<pair<lli,lli> >
#define pb push_back
#include<string>
#define mp map<string,lli>
#define mpp map<char,lli>
#define ss set<lli>
#define MOD 1000000007
//#define N 100001
#define test lli t;cin>>t;while(t--)
using namespace std;
int main()
{
test
{
lli n,k,f,x,y;
cin>>n>>k>>f;
vi arr,brr,c;
arr.pb(0),brr.pb(0);
if(n==1)
{
cin>>x>>y;
c.pb(x-0);
c.pb(f-y);
if(c[0]>=k || c[1]>=k)
cout<<"YES\n";
else
cout<<"NO\n";
}
else
{
vii a;
for(lli i=0;i<n;i++)
{
cin>>x>>y;
a.pb(make_pair(x,y));
}
sort(a.begin(),a.end());
for(auto x:a)
arr.pb(x.first),brr.pb(x.second);
for(lli i=0;i<brr.size();i++)
c.pb((arr[i+1]-brr[i]));
if(f>brr[brr.size()-1])
c.pb(f-brr[brr.size()-1]);
bool flag=false;
for(lli i=0;i<c.size();i++)
{
if(c[i]>=k)
{
flag=true;
break;
}
}
if(flag)
cout<<"YES\n";
else
cout<<"NO\n";
}
}
}
Thank you so much man!!
Does the editorial solution take overlapping intervals into consideration ?
1 Like
intervals can overlap therefore,you haven’t considered that
I tried to use prefix sum in this but it is giving me TLE custom testcase are working fine plz help
My code:
#include<bits/stdc++.h>
using namespace std;
#define int long long int
signed main()
{
int t;
cin>>t;
while(t--)
{
int n,k,f;
cin>>n>>k>>f;
vector<int> pre(f,0);
while(n--)
{
int s,e ;
cin>>s>>e;
pre[s]++;
if(e< pre.size())
pre[e]--;
}
int z=0;
if(pre[0]==0) z++;
int i=1;
for(i=1;i<f;i++)
{
pre[i]+=pre[i-1];
if(pre[i]==0)
{
z++;
if(z>=k) {cout<<"YES"<<endl; break;}
}
}
if(i==f) cout<<"NO"<<endl;
}
}
It can be less than or equal to f.
In the editorial at the place where case 3 is explained I had earlier used a format which included both extremities and I had specified it in braces that is what I am talking about being made consistent with the rest of the occurrences of interval representation. In the question [x, y] means xth minute to yth minute which means x to x+1 (first minute of interval, xth minute overall), x+1 to x+2 (x+1th minute overall), …, y-1 to y (y-1th minute overall), which means the question suggests the interval as being from x to y minutes such that the yth minute is not included but is merely the minute which when commences the interval terminates. Hope that helped, Thank you.
3 Likes
Can someone please let me what is wrong in my code i got WA.
void solve()
{
ll N,K,F;
cin>>N>>K>>F;
ll initial = 0;
ll counter = 0;
vector<pair<ll,ll>>vec;
for(ll i=0;i<N; i++)
{
ll x,y;
cin>>x>>y;
vec.push_back(make_pair(x,y));
}
sort(vec.begin(),vec.end());
for(ll i=0; i<vec.size(); i++)
{
pair<ll,ll>p = vec[i];
counter+=abs(p.second -p.first);
}
/*
for(ll i=0;i<N;i++)
{
ll S,E;
cin>>S>>E;
counter+=abs(initial-S);
initial = E;
}
*/
//cout << counter << endl;
if(abs(F-counter) >= K)
{
cout << "YES" << endl;
}
else
{
cout << "NO" << endl;
}
}
my code only passing three test cases can anybody help ? please
link to my code
https://www.codechef.com/viewsolution/47106350
can someone tell time complexity of my code…and if it’s correct…i am getting tle.>
`bool comp(pii a, pii b)
{
return (a.pf==b.pf) ? b.ps>a.ps : b.pf>a.pf;
}
int main(int argc, char const *argv[])
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
//file_i_o();
int t=1;
cin>>t;
while(t–)
{
get(n) get(k) get(f)
vector v(n);
rep(i,0,n)
{
pii a;
cin>>a.pf>>a.ps;
v[i]=a;
}
stack st;
sort(all(v),comp);
st.push(v[0]);
ll val=v[0].pf;
rep(i,1,n)
{
if(v[i].pf > (st.top()).ps)
{
val+=v[i].pf - (st.top()).ps;
st.push(v[i]);
}
else
{
(st.top()).ps=v[i].ps;
}
}
val+=f-(st.top()).ps;
if(val>=k)
{
putn(“YES”)
}
else
{
putn(“NO”)
}
}
#ifndef ONLINE_JUDGE
cerr<<"\ntime taken : "<<(float)clock()/CLOCKS_PER_SEC<<" secs"<<"\n";
#endif
return 0;
}
`
My code passes 1st and 4th subtask. I cant find what’s wrong. can someone tell where is it going wrong? thanks in advance
Yes, Thank you.
can anyone find out the error in my code ,its not passing one of the subset.