fork download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. template<typename X, typename Y>
  5. bool chmax(X& a, Y b) { return (a < b) ? a = b, 1 : 0; }
  6.  
  7. template<typename X, typename Y>
  8. bool chmin(X& a, Y b) { return (a > b) ? a = b, 1 : 0; }
  9.  
  10. using ll = long long;
  11. using ull = unsigned long long;
  12.  
  13. const int N = 1e5+5;
  14. const ull BASE = 1e6+3;
  15.  
  16. int n, a[N];
  17. ull P[N], H[N];
  18. int freq[N];
  19.  
  20. ull get_hash(int l, int r) {
  21.     return H[r] - H[l - 1] * P[r - l + 1];
  22. }
  23.  
  24. struct Info {
  25.     ull h;
  26.     int p;
  27.     bool operator<(const Info& o) const {
  28.         if (h != o.h) return h < o.h;
  29.         return p < o.p;
  30.     }
  31. };
  32.  
  33. int check(int L, int f) {
  34.     if (L > n) return -1;
  35.     vector<Info> S;
  36.     for (int i = L; i <= n; i++) S.push_back({get_hash(i - L + 1, i), i});
  37.     sort(S.begin(), S.end());
  38.     int pos = -1, cnt = 1;
  39.     for (size_t i = 1; i <= (int)S.size(); i++) {
  40.         if (i < (int)S.size() && S[i].h == S[i - 1].h) cnt++;
  41.         else {
  42.             if (cnt == f) chmax(pos, S[i - 1].p);
  43.             cnt = 1;
  44.         }
  45.     }
  46.     return pos;
  47. }
  48.  
  49. void solve() {
  50.     cin >> n;
  51.     vector<int> vals;
  52.     for (int i = 1; i <= n; i++) { 
  53.         cin >> a[i];
  54.         vals.push_back(a[i]);
  55.     }
  56.     sort(vals.begin(), vals.end());
  57.     vals.erase(unique(vals.begin(), vals.end()), vals.end());
  58.     int mx_freq = 0;
  59.     for (int i = 1; i <= n; i++) {
  60.         a[i] = lower_bound(vals.begin(), vals.end(), a[i]) - vals.begin() + 1;
  61.         freq[a[i]]++;
  62.         chmax(mx_freq, freq[a[i]]);
  63.     }
  64.     P[0] = 1;
  65.     for (int i = 1; i <= n; i++) {
  66.         P[i] = P[i - 1] * BASE;
  67.         H[i] = H[i - 1] * BASE + a[i];
  68.     }
  69.     int low = 1, high = n, best_len = 1, best_pos = n;
  70.     while (low <= high) {
  71.         int mid = low + (high - low) / 2;
  72.         int p = check(mid, mx_freq);
  73.         if (p != -1) {
  74.             best_len = mid;
  75.             best_pos = p;
  76.             low = mid + 1;
  77.         } else high = mid - 1;
  78.     }
  79.     cout << best_pos - best_len + 1 << ' ' << best_pos << '\n';
  80. }
  81.  
  82. int main() {
  83.     ios_base::sync_with_stdio(false); cin.tie(NULL);
  84.  
  85.     #define TASK "BAI4"
  86.     if (fopen(TASK".INP", "r")) {
  87.         freopen(TASK".INP", "r", stdin);
  88.         freopen(TASK".OUT", "w", stdout);
  89.     }
  90.  
  91.     int tests = 1; // cin >> tests;
  92.     while (tests--) solve();
  93.  
  94.     #ifdef LOCAL
  95.     cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
  96.     #endif
  97.     return 0;
  98. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin 
12
3 0 4 1 9 7 5 4 1 9 7 5
stdout 
8 12
https://ideone.com/EcREyr
language:
C++14 (gcc 8.3)
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!