Submission #1029297

#	Time	Username	Problem	Language	Result	Execution time	Memory
1029297		avighna	Progression (NOI20_progression)	C++17	15 / 100	3075 ms	101704 KiB

Progression

#include <bits/stdc++.h>

typedef long long ll;

class SparseTable {
public:
  ll maxPow;
  std::vector<ll> orig;
  std::vector<std::vector<ll>> table_min, table_max;

  SparseTable(const std::vector<ll> &x) {
    orig = x;
    const ll n = x.size();
    maxPow = std::floor(std::log2(n));
    table_min = std::vector<std::vector<ll>>(maxPow + 1, std::vector<ll>(n));
    table_max = std::vector<std::vector<ll>>(maxPow + 1, std::vector<ll>(n));
    for (ll i = 0; i < n; ++i) {
      table_min[0][i] = x[i];
      table_max[0][i] = x[i];
    }
    for (ll power = 1; power <= maxPow; ++power) {
      for (ll i = 0; i < n - (1 << (power - 1)); ++i) {
        table_min[power][i] =
            std::min(table_min[power - 1][i],
                     table_min[power - 1][i + (1 << (power - 1))]);
        table_max[power][i] =
            std::max(table_max[power - 1][i],
                     table_max[power - 1][i + (1 << (power - 1))]);
      }
    }
  }

  ll query_min(ll a, ll b) {
    if (a == b) {
      return orig[a];
    }
    ll powToUse = std::ceil(std::log2(b - a + 1)) - 1;
    return std::min(table_min[powToUse][a],
                    table_min[powToUse][b - (1 << powToUse) + 1]);
  }
  ll query_max(ll a, ll b) {
    if (a == b) {
      return orig[a];
    }
    ll powToUse = std::ceil(std::log2(b - a + 1)) - 1;
    return std::max(table_max[powToUse][a],
                    table_max[powToUse][b - (1 << powToUse) + 1]);
  }
};

ll BinarySearchMax(ll s, ll e, const std::function<bool(ll)> &f) {
  ll ans = s;
  while (s <= e) {
    ll m = s + (e - s) / 2;
    if (f(m)) {
      ans = m;
      s = m + 1;
    } else {
      e = m - 1;
    }
  }
  return ans;
}

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);

  ll n, q;
  std::cin >> n >> q;
  std::vector<ll> d(n);
  for (auto &i : d) {
    std::cin >> i;
  }

  while (q--) {
    ll t;
    std::cin >> t;
    ll l, r;
    std::cin >> l >> r;
    --l, --r;
    if (t == 1) {
      ll s, c;
      std::cin >> s >> c;
      for (ll i = l; i <= r; ++i) {
        d[i] += s + (i - l) * c;
      }
    } else if (t == 2) {
      ll s, c;
      std::cin >> s >> c;
      for (ll i = l; i <= r; ++i) {
        d[i] = s + (i - l) * c;
      }
    } else {
      std::vector<ll> diff(n);
      std::adjacent_difference(d.begin(), d.end(), diff.begin());
      SparseTable table(diff);
      ll ans = 1;
      if (l == r) {
        std::cout << ans << '\n';
        continue;
      }
      for (ll i = l; i <= r; ++i) {
        ans =
            std::max(ans, BinarySearchMax(i + 1, r,
                                          [&](ll m) {
                                            return table.query_min(i + 1, m) ==
                                                   table.query_max(i + 1, m);
                                          }) -
                              i + 1);
      }
      std::cout << ans << '\n';
    }
  }
}

• Subtask 1: 0 / 9
• Subtask 2: 15 / 15
• Subtask 3: 0 / 35
• Subtask 4: 0 / 11
• Subtask 5: 0 / 13
• Subtask 6: 0 / 17