Submission #68824203

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;
using LL = long long;

const int kMaxN = 1.5e6 + 5, kMaxS = 2e5 + 5;

LL a[kMaxN], f[kMaxN], w[kMaxN << 2], tag[kMaxN << 2], n, s;
vector<int> pos[kMaxS];

void Init() {
  for (int i = 1; i <= n; i++) {
    pos[a[i]].push_back(i);
  }
}

LL Nxt(LL x, int y) {
  int p = x % n;
  if (p >= *pos[y].rbegin()) {
    return x / n * n + pos[y][0] + n;
  } else {
    int l = 0, r = pos[y].size() - 1;
    for (int mid; l < r; p < pos[y][mid] ? r = mid : l = mid + 1) {
      mid = l + r >> 1;
    }
    return x / n * n + pos[y][r];
  }
}

LL Pre(LL x, int y) {
  int p = x % n;
  if (p < *pos[y].begin()) {
    return x / n * n + pos[y][pos[y].size() - 1] - n;
  } else {
    int l = 0, r = pos[y].size() - 1;
    for (int mid; l < r; p >= pos[y][mid] ? l = mid : r = mid - 1) {
      mid = l + r + 1 >> 1;
    }
    return x / n * n + pos[y][l];
  }
}

void Add(int u, LL x) {
  w[u] = max(w[u], x), tag[u] = max(tag[u], x);
}

void PushDown(int u) {
  if (tag[u]) {
    Add(u << 1, tag[u]);
    Add(u << 1 | 1, tag[u]);
    tag[u] = 0;
  }
}

void Update(int u, int l, int r, int L, int R, LL x) {
  if (l > R || r < L) {
    return;
  } else if (L <= l && r <= R) {
    Add(u, x);
  } else {
    int mid = l + r >> 1;
    PushDown(u);
    Update(u << 1, l, mid, L, R, x);
    Update(u << 1 | 1, mid + 1, r, L, R, x);
    w[u] = max(w[u << 1], w[u << 1 | 1]);
  }
}

LL Query(int u, int l, int r, int L, int R) {
  if (l > R || r < L) {
    return 0;
  } else if (L <= l && r <= R) {
    return w[u];
  } else {
    int mid = l + r >> 1;
    PushDown(u);
    return max(Query(u << 1, l, mid, L, R), Query(u << 1 | 1, mid + 1, r, L, R));
  }
}

void Solve(int l, int r) {
  if (l == r) {
    return;
  } else {
    int mid = l + r >> 1;
    Solve(l, mid);
    for (int k = 1; k <= r - l; k++) {
      int len = min(r - k, mid);
      int pl = max(mid + 1, (int)(lower_bound(f + l, f + len + 1, Pre(f[len], k)) - f) + k);
      int pr = min(r, mid + k);
      Update(1, 0, s, pl, pr, Nxt(f[len], k));
    }
    for (int i = mid + 1; i <= r; i++) {
      f[i] = Query(1, 0, s, i, i);
    }
    Solve(mid + 1, r);
  }
}

int main() {
  ios ::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n >> s;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  Init();
  Solve(0, s);
  cout << f[s];
  return 0;
}

Submission Info

Compile Error

Main.cpp: In function ‘LL Nxt(LL, int)’:
Main.cpp:24:15: warning: suggest parentheses around ‘+’ inside ‘>>’ [-Wparentheses]
   24 |       mid = l + r >> 1;
      |             ~~^~~
Main.cpp: In function ‘LL Pre(LL, int)’:
Main.cpp:37:19: warning: suggest parentheses around ‘+’ inside ‘>>’ [-Wparentheses]
   37 |       mid = l + r + 1 >> 1;
      |             ~~~~~~^~~
Main.cpp: In function ‘void Update(int, int, int, int, int, LL)’:
Main.cpp:61:17: warning: suggest parentheses around ‘+’ inside ‘>>’ [-Wparentheses]
   61 |     int mid = l + r >> 1;
      |               ~~^~~
Main.cpp: In function ‘LL Query(int, int, int, int, int)’:
Main.cpp:75:17: warning: suggest parentheses around ‘+’ inside ‘>>’ [-Wparentheses]
   75 |     int mid = l + r >> 1;
      |               ~~^~~
Main.cpp: In function ‘void Solve(int, int)’:
Main.cpp:85:17: warning: suggest parentheses around ‘+’ inside ‘>>’ [-Wparentheses]
   85 |     int mid = l + r >> 1;
      |               ~~^~~

Judge Result