fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using ULL = unsigned long long;
  5.  
  6. int main(){
  7.     ios::sync_with_stdio(false);
  8.     cin.tie(nullptr);
  9.     int T; 
  10.     if (!(cin >> T)) return 0;
  11.     while (T--) {
  12.         int n; cin >> n;
  13.         vector<int> a(n);
  14.         for (int i = 0; i < n; ++i) cin >> a[i];
  15.  
  16.         vector<int> vals = a;
  17.         sort(vals.begin(), vals.end());
  18.         vals.erase(unique(vals.begin(), vals.end()), vals.end());
  19.         for (int i = 0; i < n; ++i)
  20.             a[i] = lower_bound(vals.begin(), vals.end(), a[i]) - vals.begin();
  21.         int M = (int)vals.size();
  22.         int W = (M + 63) / 64;
  23.  
  24.         vector<int> maxEnd(n, -1);
  25.         vector<vector<int>> seqAt(n);
  26.         vector<ULL> prefMasksAt_flat;
  27.         vector<int> prefOffset(n+1,0);
  28.         prefOffset[0] = 0;
  29.  
  30.         for (int s = 0; s < n; ++s) {
  31.             vector<ULL> cur(W, 0ULL);
  32.             vector<int> seq;
  33.             vector<ULL> store;
  34.             vector<char> seen(M, 0);
  35.             for (int j = s; j < n; ++j) {
  36.                 int c = a[j];
  37.                 if (seen[c]) break;
  38.                 seen[c] = 1;
  39.                 seq.push_back(c);
  40.                 int idx = c >> 6;
  41.                 int bit = c & 63;
  42.                 cur[idx] |= (1ULL << bit);
  43.                 for (int t = 0; t < W; ++t) store.push_back(cur[t]);
  44.             }
  45.             seqAt[s] = move(seq);
  46.             prefOffset[s+1] = prefOffset[s] + (int)store.size();
  47.             for (auto &v : store) prefMasksAt_flat.push_back(v);
  48.             maxEnd[s] = s + (int)seqAt[s].size() - 1;
  49.         }
  50.  
  51.         auto get_pref_mask_ptr = [&](int s, int prefix_idx)->ULL* {
  52.             if (prefix_idx < 0) return nullptr;
  53.             int off = prefOffset[s] + prefix_idx * W;
  54.             return &prefMasksAt_flat[off];
  55.         };
  56.  
  57.         vector<vector<int>> seqEndAt(n);
  58.         for (int r = 0; r < n; ++r) {
  59.             vector<char> seen(M, 0);
  60.             vector<int> seq;
  61.             for (int j = r; j >= 0; --j) {
  62.                 int c = a[j];
  63.                 if (seen[c]) break;
  64.                 seen[c] = 1;
  65.                 seq.push_back(c);
  66.             }
  67.             seqEndAt[r] = move(seq);
  68.         }
  69.  
  70.         int ans = 0;
  71.         vector<int> lenStart(n);
  72.         for (int s = 0; s < n; ++s) lenStart[s] = (int)seqAt[s].size();
  73.  
  74.         vector<int> suffixMaxStartLen(n+1, 0);
  75.         for (int i = n-1; i >= 0; --i) suffixMaxStartLen[i] = max(suffixMaxStartLen[i+1], lenStart[i]);
  76.  
  77.         vector<ULL> maskL(W);
  78.  
  79.         for (int r = 0; r < n; ++r) {
  80.             fill(maskL.begin(), maskL.end(), 0ULL);
  81.             int maxT = (int)seqEndAt[r].size();
  82.             for (int t = 1; t <= maxT; ++t) {
  83.                 int c = seqEndAt[r][t-1];
  84.                 maskL[c >> 6] |= (1ULL << (c & 63));
  85.                 int leftLen = t;
  86.                 int l = r - (t - 1);
  87.                 int ub = leftLen + suffixMaxStartLen[r+1];
  88.                 if (ub <= ans) continue;
  89.                 for (int s = r+1; s < n; ++s) {
  90.                     int maxPref = lenStart[s];
  91.                     if (maxPref == 0) continue;
  92.                     if (leftLen + maxPref <= ans) continue;
  93.                     int lo = 0, hi = maxPref - 1, best = -1;
  94.                     while (lo <= hi) {
  95.                         int mid = (lo + hi) >> 1;
  96.                         ULL *pm = get_pref_mask_ptr(s, mid);
  97.                         bool ok = true;
  98.                         for (int w = 0; w < W; ++w) {
  99.                             if ((pm[w] & maskL[w]) != 0ULL) { ok = false; break; }
  100.                         }
  101.                         if (ok) { best = mid; lo = mid + 1; }
  102.                         else hi = mid - 1;
  103.                     }
  104.                     if (best >= 0) {
  105.                         int rightLen = best + 1;
  106.                         ans = max(ans, leftLen + rightLen);
  107.                     }
  108.                 }
  109.             }
  110.         }
  111.  
  112.         cout << ans << '\n';
  113.     }
  114.  
  115.     return 0;
  116. }
  117.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
2
6
1 2 3 2 3 1
5
1 2 3 4 5
stdout
copy 
3
5
https://ideone.com/xHu77A
language:
C++14 (gcc 8.3)
created:
2 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!