fork download
copy 
  1. #include<bits/stdc++.h> //NeOWami
  2. using namespace std;
  3.  
  4. #define int long long
  5. #define ft first
  6. #define sc second
  7. using pii = pair<int, int>;
  8. const int N = 2e5 + 5;
  9. using ull = unsigned long long;
  10. const ull BASE = 200003;
  11. int n, q;
  12. int a[N];
  13. void compress() {
  14.     vector<int> tmp;
  15.     for (int i = 1; i <= n; i++) {
  16.         tmp.push_back(a[i]);
  17.     }
  18.     sort(tmp.begin(), tmp.end());
  19.     tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end());
  20.     for (int i = 1; i <= n; i++) a[i] = lower_bound(tmp.begin(), tmp.end(), a[i]) - tmp.begin() + 1;
  21. }
  22. namespace sub1 {
  23. int calc(int l, int r) {
  24.     if (l > r) return 0;
  25.     set<vector<int>> S;
  26.     vector<int> lst;
  27.     for (int i =l; i <= r; i++) lst.push_back(a[i]);
  28.     S.insert(lst);
  29.     int len = r - l + 1;
  30.     for (int i = 0; i < len; i++) {
  31.         for (int j = i + 1; j < len; j++) {
  32.             reverse(lst.begin() + i, lst.begin() + j + 1);
  33.             S.insert(lst);
  34.             reverse(lst.begin() + i, lst.begin() + j + 1);
  35.         }
  36.     }
  37. //    cerr << l << " " << r << ":\n";
  38. //    for (vector<int> d: S) {
  39. //        for (int i: d) cerr << i << " "; cerr << "\n";
  40. //    }
  41.     return S.size();
  42. }
  43. void solve() {
  44.     while(q--) {
  45.         int id; cin >> id;
  46.         a[id] = 0;
  47.         int ans = 0;
  48.         for (int l = 1, r = 1; r <= n; r++) {
  49.             if (a[r] == 0) {
  50.                 ans = max(ans, calc(l, r - 1));
  51.                 l = r + 1;
  52.             }
  53.  
  54.             if (r == n && a[r]) ans = max(ans, calc(l, r));
  55.         }
  56.         cout << ans << "\n";
  57.     }
  58. }
  59. }///
  60. namespace sub2 {
  61. ull S[N], T[N], POW[N];
  62. ull GS(int l, int r) {
  63.     if (l > r) return 0;
  64.     return S[r] - S[l - 1] * POW[r - l + 1];
  65. }
  66. ull GT(int l, int r) {
  67.     if (l > r) return 0;
  68.     return T[l] - T[r + 1] * POW[r - l + 1];
  69. }
  70.  
  71. int calc(int l, int r) {
  72.     if (l > r) return 0;
  73.     set<ull> s;
  74.     s.insert(GS(l, r));
  75.     for (int i = l; i <= r; i++) {
  76.         for (int j = i + 1; j <= r; j++) {
  77.             ull val = GS(l, i - 1) * POW[r - (i - 1 + 1) + 1] + GT(i, j) * POW[r - (j + 1) + 1] + GS(j + 1, r);
  78.             s.insert(val);
  79.         }
  80.     }
  81.     return s.size();
  82. }
  83.  
  84. void solve() {
  85.     POW[0] = 1;
  86.     for (int i = 1; i <= n;i++) POW[i] = POW[i -1 ] * BASE;
  87.     for (int i = 1; i <= n; i++) S[i] = S[i -1 ] * BASE + a[i];
  88.     for (int i = n; i >= 1; i--) T[i] = T[i +1 ] * BASE + a[i];
  89.  
  90.     while(q--) {
  91.         int id; cin >> id;
  92.         a[id] = 0;
  93.         int ans = 0;
  94.         for (int l = 1, r = 1; r <= n; r++) {
  95.             if (a[r] == 0) {
  96.                 ans = max(ans, calc(l, r - 1));
  97.                 l = r + 1;
  98.             }
  99.  
  100.             if (r == n && a[r]) ans = max(ans, calc(l, r));
  101.         }
  102.         cout << ans << "\n";
  103.     }
  104. }
  105. }///
  106. signed main() {
  107.     cin.tie(NULL)->sync_with_stdio(false); cout.tie(NULL);
  108.     if (ifstream("TET.inp")) {
  109.         freopen("TET.inp", "r", stdin);
  110.         freopen("TET.out", "w", stdout);
  111.     }
  112.     cin >> n >> q;
  113.     for (int i = 1; i <= n; i++) cin >> a[i];
  114.     compress();
  115. //    for (int i= 1; i <= n; i++) cerr << a[i] << " "; cerr << "\n";
  116.     return sub2::solve(), 0;
  117. //    if (n <= 200 && q == 1) return sub1::solve(), 0;
  118. //    if (n <= 2000 && q == 1) return sub1::solve(), 0;
  119.     return 0;
  120. }
  121.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/i2Izcf
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!