Guest User

MAXREMOV Author

a guest
Feb 17th, 2019
685
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // Author : Abhinav Jain
  2. // Institution: Jaypee Institute of information Technology
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5. #define lli long long int
  6. #define cases lli testcases;cin>>testcases; while(testcases--)
  7. #define trace(x) cerr << '>' << #x << ':' << x << endl;
  8.  
  9. lli l[100005],r[100005],A[100005];
  10. lli prefixK[100005];//prefixK[i]= stores the cnt of K from 1 to i
  11. lli postfixK[100005];//postfixK[i]= stores the cnt of K from i to M
  12. lli cmkOne[100005];//cmkOne[i]= stores the cnt of (K+1) from 1 to i
  13. lli n,k;
  14. int32_t main()
  15. {
  16.     cases
  17.     {
  18.         lli i,j,AC=0;
  19.         memset(A,0,sizeof(A));
  20.         memset(prefixK,0,sizeof(prefixK));
  21.         memset(postfixK,0,sizeof(postfixK));
  22.         memset(cmkOne,0,sizeof(cmkOne));
  23.         cin>>n>>k;
  24.         for(i=0;i<n;i++)
  25.         {
  26.             cin>>l[i]>>r[i];// 1 based indexing
  27.             A[l[i]]++;
  28.             A[r[i]+1]--;
  29.         }
  30.         // Array A contains the array after performing all the N operations.
  31.         for(i=1;i<=100001;++i)
  32.         {
  33.           A[i]=A[i]+A[i-1];
  34.           cmkOne[i] = (A[i]==k+1) + cmkOne[i-1];
  35.           prefixK[i]=(A[i]==k)+ prefixK[i-1];
  36.         }
  37. //      for(i=1;i<=11;i++)cout<<A[i]<<" ";cout<<endl;
  38.         for(i=100000;i>=1;i--)
  39.         {
  40.             postfixK[i]=postfixK[i+1]+ (A[i]==k);
  41.         }
  42.         // Now checking by removing each range one by one.
  43.         for(i=0;i<n;i++)
  44.         {
  45.           lli val=0,x=l[i],y=r[i];
  46.           lli Kcnt=cmkOne[y]-cmkOne[x]+(A[x]==k+1);
  47.           Kcnt+=prefixK[x-1]+postfixK[y+1];
  48.           AC=max(AC,Kcnt);
  49.           //trace(Kcnt);
  50.         }
  51.          cout<<AC<<endl;
  52.     }
  53.     #ifndef ONLINE_JUDGE
  54.     cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n\n";
  55.     #endif
  56. return 0;
  57. }
RAW Paste Data