Advertisement
Misbah_Uddin_Tareq

Two pointer by nayem vai

May 31st, 2020
81
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.80 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define Ore_Batpar___Ore_Batpar     ios_base :: sync_with_stdio(false);
  4. #define ll                          long long
  5. #define MAXN                        200007
  6.  
  7. bool comp (pair <ll, pair <ll, ll> > p, pair <ll, pair <ll, ll> > q)
  8. {
  9.     if (p.first == q.first) return p.second.first < q.second.first;
  10.     return p.first < q.first;
  11. }
  12.  
  13. int main ()
  14. {
  15.     Ore_Batpar___Ore_Batpar
  16.  
  17.     int test_case; cin >> test_case;
  18.     for (int t = 1; t <= test_case; t++)
  19.     {
  20.         set <ll> Set;
  21.         ll n, currUnique = 0; cin >> n;
  22.         vector <ll> vec(n);
  23.         vector < pair <ll, pair <ll, ll> > > res;
  24.         map <ll, ll> cnt;
  25.         for (int i = 0; i<n; i++) {cin >> vec[i]; Set.insert(vec[i]);}
  26.  
  27.         ll k = Set.size(), i = 0, j = 0;
  28.  
  29.         if (k == 1) {cout << "Case " << t << ": " << 0 << " " << 0 << endl; continue;}
  30.  
  31.         while(j < n)
  32.         {
  33.             if (cnt[vec[j]] == 0) currUnique++;
  34.             cnt[vec[j]]++;
  35.  
  36.             //cout << "maIN i : " << i << " J : " << j << " CurUn : " << currUnique << endl;
  37.  
  38.             if (currUnique == k)
  39.             {
  40.                 //cout << "Inside of that loop" << endl;
  41.                 while(i < j)
  42.                 {
  43.                     cnt[vec[i]]--;
  44.                     if (cnt[vec[i]] == 0)
  45.                     {
  46.                         currUnique--;
  47.                         res.push_back({(j - i + 1), {i, j}});
  48.                         //cout << "I : " << i << " J : " << j << endl;
  49.                         i++;
  50.                         break;
  51.                     }
  52.                     i++;
  53.                 }
  54.             }
  55.             j++;
  56.         }
  57.         sort(res.begin(), res.end(), comp);
  58.         cout << "Case " << t << ": " << res[0].second.first << " " << res[0].second.second << endl;
  59.     }
  60.  
  61.  
  62.     return 0;
  63. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement