Guest User

MAXREMOV Tester

a guest
Feb 17th, 2019
455
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.     #include <bits/stdc++.h>
  2.      
  3.     using namespace std;
  4.      
  5.     const int MX = (1<<20);
  6.      
  7.     int T;
  8.      
  9.     int cakes = 100000 , queries , tar;
  10.      
  11.     int heights[MX];
  12.      
  13.     int tarcnt[MX] , tarpluscnt[MX];
  14.      
  15.     pair < int , int > Query[MX];
  16.      
  17.     int main(){
  18.      
  19.         scanf("%d",&T);
  20.      
  21.         while(T--){
  22.      
  23.             scanf("%d %d",&queries,&tar);
  24.      
  25.             for(int j = 1 ; j <= cakes ; j++) heights[j] = 0;
  26.      
  27.             for(int j = 1 ; j <= queries ; j++){
  28.                 int l , r;
  29.                 scanf("%d %d",&l,&r);
  30.                 Query[j] = {l , r};
  31.                 heights[l]++;
  32.                 heights[r+1]--;
  33.             }
  34.      
  35.             for(int j = 1 ; j <= cakes ; j++){
  36.      
  37.                 heights[j] += heights[j-1];
  38.      
  39.                 tarcnt[j] = tarcnt[j-1];
  40.      
  41.                 if(heights[j] == tar) ++tarcnt[j];
  42.      
  43.                 tarpluscnt[j] = tarpluscnt[j-1];
  44.      
  45.                 if(heights[j] == tar + 1) ++tarpluscnt[j];
  46.             }
  47.      
  48.             int ans = 0;
  49.      
  50.             for(int j = 1 ; j <= queries ; j++){
  51.                 int l = Query[j].first , r = Query[j].second;
  52.                 ans = max(ans , tarcnt[l-1] +
  53.                                 tarcnt[cakes] - tarcnt[r] +
  54.                                 tarpluscnt[r] - tarpluscnt[l - 1]
  55.                         );
  56.             }
  57.      
  58.             cout<<ans<<endl;
  59.      
  60.         }
  61.      
  62.      
  63.     }
RAW Paste Data