Submission #1185724

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185724		Gurban	Sequence (APIO23_sequence)	C++20	32 / 100	446 ms	47944 KiB

sequence

/**
*    In the name of Allah
*    We are nothing and you're everything
**/
#include <bits/stdc++.h>
#include "sequence.h"
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
//#define int long long

const int mod = 1e9+9;
using namespace std;
using ll = long long;

const int inf = 1e9+7;
pair<int, int> neutral = {inf, -inf};

pair<int, int> operator+(const pair<int, int> &a, const pair<int, int> &b) {
    return {min(a.first, b.first), max(a.second, b.second)};
}

struct segtree {
  vector<pair<int, int>> tree;
  vector<int> gos;
  int size = 1;
  
  void init(int n) {
    //size = 1;
    while (size < n)size <<= 1;
    tree.assign(2*size-1, {0, 0});
    gos.assign(2*size-1, 0);
  }
  
  void apply(int l, int r, int v, int x, int lx, int rx) {
    if (rx <= l || r <= lx)return;
    if (lx >= l && rx <= r) {
      gos[x] += v;
      tree[x].first += v, tree[x].second += v;
      return;
    }
    
    int mid = lx + rx >> 1;
    
    apply(l, r, v, 2*x+1, lx, mid), apply(l, r, v, 2*x+2, mid, rx);
    tree[x] = tree[2*x+1]+tree[2*x+2];
    tree[x].first += gos[x], tree[x].second += gos[x];
  }
  
  void apply(int l, int r, int v) {
    apply(l, r, v, 0, 0, size);
  }
  
  pair<int, int> get(int l, int r, int x, int lx, int rx) {
    if (rx <= l || r <= lx)return neutral;
    if (lx >= l && rx <= r)return tree[x];
    
    int mid = lx + rx >> 1;
    
    pair<int, int> s1 = get(l, r, 2*x+1, lx, mid) + get(l, r, 2*x+2, mid, rx);
    s1.first += gos[x], s1.second += gos[x];
    return s1;  
    }
  
  pair<int, int> get(int l, int r) {
    return get(l, r, 0, 0, size);
  }
};

int sequence(int n, vector<int> a) {
  vector<pair<int, int>> cnt(n+1, {-1, -1});
  for (int i = 0; i < n; ++i) {
    int x = a[i];
    if (cnt[x].first == -1)cnt[x].first = i;
    else cnt[x].second = i;
  }

  vector<int> adj[n+1];
  for (int i = 0; i < n; ++i)
    adj[a[i]].push_back(i);
  
  segtree st;
  st.init(n+1);
  
  for (int i = 0; i < n; ++i) {
    st.apply(i, n, 1);
  }
  
  int ans = 1;
  for (int i = 1; i <= n; ++i) {
    int x = i;
    if (sz(adj[x]) <= ans) {
      for (auto j: adj[x])
        st.apply(j, n, -2);
      continue;
    }
    
    for (int j:adj[x])
      st.apply(j, n, -1);
      
    
    for (int j = sz(adj[x])-1; j >= 0; --j) {
      while (j + ans < sz(adj[x])) {
        pair<int, int> l = st.get(0, adj[i][j]);
        pair<int, int> r = st.get(adj[i][j+ans], n);
        
        if (r.first >= -ans-1 && r.first <= ans+1) {
          ans += 1;
          continue;
        }
        if (r.second >= -ans-1 && r.second <= ans+1) {
          ans += 1;
          continue;
        }
        l.first -= (ans+1), l.second += ans+1;
        if (max(l.first, r.first) <= min(r.second, l.second))ans++;
        else break;
      }
    }
    for (auto j: adj[x])
      st.apply(j, n, -1);
  }
  
  return ans;
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 17
• Subtask 3: 7 / 7
• Subtask 4: 12 / 12
• Subtask 5: 13 / 13
• Subtask 6: 0 / 22
• Subtask 7: 0 / 18