fork download
copy 
  1. #include <bits/stdc++.h> 
  2.  
  3. using namespace std;
  4.  
  5. #define endl "\n" 
  6. typedef long long int ll;
  7. typedef vector<int> vi;
  8.  
  9.  
  10. int main(){
  11.     int t;
  12.     cin>>t;
  13.  
  14.     for(int testcase=0; testcase<t; testcase++){
  15.         int n, d, k; cin>>n>>d>>k;
  16.  
  17.         vector<int> st (n+1, 0);
  18.         vector<int> end (n+1, 0);
  19.  
  20.         for (int i = 0; i < k; i++)
  21.         {   
  22.             int x, y;
  23.             cin>>x>>y;
  24.             ++st[--x];
  25.             ++end[--y];	//already sorted
  26.         }
  27.  
  28.         int res=0, res2=0;
  29.  
  30.         int idx=0; int endidx=0;
  31.         int window = 0;
  32.         for (int i = 0; i < d; i++)
  33.         {
  34.             if(st[i]>0) {window+=st[i]; }
  35.         }
  36.  
  37.         int mx = window, mn =window;
  38.         for (int i = d; i < n; i++)
  39.         {
  40.            if(end[i-d]>0) {window-=end[i-d]; }
  41.  
  42.             if(st[i]>0) {window+=st[i]; }
  43.  
  44.             if(window>mx) {res = (i-d+1); mx = window;}
  45.             if(window<mn) {res2 = (i-d+1); mn = window;}
  46.         }
  47.  
  48.         cout<<res+1<<" "<<res2+1<<endl;
  49.     }
  50.  
  51.     return 0;
  52. }
Success #stdin #stdout 0.01s 5264KB
comments (?)
stdin
copy 
6
2 1 1
1 2
4 1 2
1 2
2 4
7 2 3
1 2
1 3
6 7
5 1 2
1 2
3 5
9 2 1
2 8
9 2 4
7 9
4 8
1 3
2 3
stdout
copy 
1 1
2 1
1 4
1 1
1 1
3 4
https://ideone.com/u0ILPD
language:
C++14 (clang 8.0)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!