Guest User

Untitled

a guest
Jan 11th, 2016
6,071
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.76 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define forn(i, n) for (int i = 0; i < int(n); i++)
  4. #define ford(i, n) for (int i = int(n) - 1; i >= 0; i--)
  5. #define fore(i, l, r) for (int i = int(l); i < int(r); i++)
  6. #define correct(x, y, n, m) (0 <= (x) && (x) < (n) && 0 <= (y) && (y) < (m))
  7. #define all(a) (a).begin(), (a).end()
  8. #define sz(a) int((a).size())
  9. #define pb(a) push_back(a)
  10. #define mp(x, y) make_pair((x), (y))
  11. #define x first
  12. #define y second
  13.  
  14. using namespace std;
  15.  
  16. typedef long long li;
  17. typedef long double ld;
  18. typedef pair<int, int> pt;
  19.  
  20. template<typename X> inline X abs(const X& a) { return a < 0? -a: a; }
  21. template<typename X> inline X sqr(const X& a) { return a * a; }
  22.  
  23. const int INF = int(1e9);
  24. const li INF64 = li(1e18);
  25. const ld EPS = 1e-9, PI = 3.1415926535897932384626433832795;
  26.  
  27. const int N = 1200300;
  28.  
  29. int n, k;
  30. int a[N];
  31.  
  32. inline bool read() {
  33.     if (!(cin >> n >> k)) return false;
  34.     forn(i, n) assert(scanf("%d", &a[i]) == 1);
  35.     return true;
  36. }
  37.  
  38. int cur;
  39. int cnt[N];
  40.  
  41. inline void add(int x) {
  42.     if (++cnt[x] == 1) cur++;
  43. }
  44.  
  45. inline void rem(int x) {
  46.     if (--cnt[x] == 0) cur--;
  47. }
  48.  
  49. inline void solve() {
  50.     cur = 0;
  51.     memset(cnt, 0, sizeof(cnt));
  52.  
  53.     int al = -1, ar = -1;
  54.     int p = 0;
  55.     forn(i, n) {
  56.         while (p < n) {
  57.             add(a[p]);
  58.             if (cur > k) {
  59.                 rem(a[p]);
  60.                 break;
  61.             }
  62.             p++;
  63.         }
  64.         if (ar - al < p - i) al = i, ar = p;
  65.         rem(a[i]);
  66.         //cerr << i << ' ' << p << endl;
  67.     }
  68.     assert(al != -1);
  69.     cout << al + 1 << ' ' << ar << endl;
  70. }
  71.  
  72. int main() {
  73. #ifdef SU1
  74.     assert(freopen("input.txt", "rt", stdin));
  75.     //assert(freopen("output.txt", "wt", stdout));
  76. #endif
  77.    
  78.     cout << setprecision(10) << fixed;
  79.     cerr << setprecision(5) << fixed;
  80.  
  81.     while (read()) {
  82.         solve();
  83.         //break;
  84.     }
  85.    
  86.     return 0;
  87. }
Advertisement
Add Comment
Please, Sign In to add comment