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.
Corner Case : If a pair is present where Si = Ei, eg. {4,4} ; {5,5}.
Then just don’t consider the pair even while taking the input into a vector or set.
The reason is because , here the k value ranges from 0 to 1e9 . Hence , your worst time complexity is O(1e9) which is not possible to compute . Hence , a TLE.
Thanks for the time
For those who are wondering why to sort…
Take this test case for example:
1
3 3 10
2 5
3 6
1 9
If not sorted then the result will be “yes” but it should be “no”.
2 Likes
Just sort the intervals in increasing order on the basis of start time and then merge them.
from the list of interval obtained subtract the duration of each interval of the list from total minutes(F) and check if the F >= K for affirmation or negation.
Can anyone tell me at which testCase my Code is getting WA ??
#include <bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL);
#define time cerr<<"Time taken : " <<(float)clock()/CLOCKS_PER_SEC <<" secs"<<"\n" ;
#define F first
#define S second
#define pb push_back
typedef long long int ll ;
#define INF 1e15
#define MOD (int)1e9+0
ll GCD (ll a , ll b) {
if (b == 0) {
return a ;
}
return GCD(b , a % b) ;
}
ll LCM(ll a , ll b) {
return (a * b) / GCD(a , b) ;
}
void solve() {
ll n , k, f ;
cin >> n >> k >> f;
vector<pair<ll,ll>>vp ;
for(ll i=0 ; i < n ; i++){
ll a,b ;
cin >> a >> b ;
vp.pb({a,b}) ;
}
for(auto p: vp){
if(p.F == 0 && p.S == f){
cout <<"NO\n" ;
return ;
}
}
ll d2 = vp[0].F ;
if(d2 >= k){
cout << "YES\n" ;
return ;
}
ll d1 = f - vp[n-1].S ;
if(d1 >= k){
cout << "YES\n" ;
return ;
}
ll sum = 0 ;
for(ll i =1 ;i<n ;i++){
ll diff = vp[i].F - vp[i-1].S ;
// cout << diff <<"\n" ;
if(diff > 0){
sum+=diff ;
}
}
if(sum >= k){
cout <<"YES\n" ;
return ;
}
cout <<"NO\n" ;
}
int32_t main() {
fast ; time;
#ifndef ONLINE_JUDGE
freopen("input.txt" , "r" , stdin) ;
freopen("output.txt" , "w" , stdout) ;
#endif
ll t = 1;
cin >> t;
while (t--) {
solve() ;
}
return 0 ;
}Hey @sky_nik
I did consider the cases where more than one invigilators are monitoring, pls help me know where i went wrong 
//સહજ
//www.linkedin.com/in/sahaj-patel-2b0b3920b/
#define ll long long
#include iostream> // i did not keep < cause it didnt appear in blog
#include map>
#include vector>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int T; cin>>T;
while(T--){
int n, k ,f;
cin>>n>>k>>f;
int s, e;
map<int, int> m;
for(int i=0; i<n; i++){
cin>>s>>e;
m[s] = e;
}
map<int, int> :: iterator it = m.begin();
int minist = it->first;
int maxilim = it->second;
int montime = 0;
it = m.begin();
it++;
for(; it!=m.end(); it++){
if(it->first < maxilim){
if(it->second <maxilim){
continue;
}
else if(it->second > maxilim){
maxilim = it->second;
}
}
else{
montime += maxilim - minist;
minist = it->first;
maxilim = it->second;
}
}
montime += maxilim - minist;
cout<<montime<<endl;
if(f-montime>=k) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return 0;
}