結果

問題 No.3305 Shift Sort
ユーザー comavius
提出日時 2025-10-05 16:36:42
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 643 ms / 2,000 ms
コード長 12,016 bytes
コンパイル時間 7,071 ms
コンパイル使用メモリ 348,464 KB
実行使用メモリ 23,972 KB
最終ジャッジ日時 2025-10-05 16:37:04
合計ジャッジ時間 21,583 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <queue>
#include <random>
#pragma region // inclusion and optimization
#ifdef IS_TEST
const bool IS_TEST_ENVIROMENT = true;
#else
const bool IS_TEST_ENVIROMENT = false;
#endif
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma endregion // inclusion and optimization

#include <bits/stdc++.h>
#pragma region // comavius::competitive library

namespace comavius::competitive { // typedefs

#pragma region // long long
typedef long long ll;
typedef std::vector<ll> vll;
typedef std::vector<vll> vvll;
typedef std::vector<vvll> vvvll;
typedef std::map<ll, ll> mll;
typedef std::map<ll, mll> mmll;
typedef std::pair<ll, ll> pll;
typedef std::vector<pll> vpll;
#pragma endregion // long long

#pragma region // long double
typedef long double ld;
typedef std::vector<ld> vld;
typedef std::vector<vld> vvld;
typedef std::vector<vvld> vvvld;
#pragma endregion // long double

#pragma region // std::string
typedef std::string str;
typedef std::vector<str> vstr;
typedef std::vector<vstr> vvstr;
typedef std::vector<vvstr> vvvstr;
#pragma endregion // std::string

#pragma region // bool
typedef std::vector<bool> vb;
typedef std::vector<vb> vvb;
typedef std::vector<vvb> vvvb;
#pragma endregion // bool

#pragma region // char
typedef std::vector<char> vc;
typedef std::vector<vc> vvc;
typedef std::vector<vvc> vvvc;
#pragma endregion // char

#pragma region // container of std
#pragma region // std::vector
template <typename T> using vec = std::vector<T>;
template <typename T> using vec2 = std::vector<std::vector<T>>;
template <typename T> using vec3 = std::vector<std::vector<std::vector<T>>>;
template <typename T>
using vec4 = std::vector<std::vector<std::vector<std::vector<T>>>>;
template <typename T>
using vec5 = std::vector<std::vector<std::vector<std::vector<std::vector<T>>>>>;
template <typename T>
using vec6 = std::vector<
    std::vector<std::vector<std::vector<std::vector<std::vector<T>>>>>>;
template <typename T>
using vec7 = std::vector<std::vector<
    std::vector<std::vector<std::vector<std::vector<std::vector<T>>>>>>>;
#pragma endregion // std::vector
#pragma endregion // container of std

} // namespace comavius::competitive

namespace comavius::competitive { // UnionFind

class UnionFind {
  std::vector<long long> parent;
  std::vector<long long> rank;
  std::vector<long long> size;
  std::vector<long long> edge_count;

public:
  UnionFind(long long num_nodes) {
    parent.resize(num_nodes, -1);
    rank.resize(num_nodes, 0);
    size.resize(num_nodes, 1);
    edge_count.resize(num_nodes, 0);
  }

  long long root_of(long long x) {
    if (parent[x] == -1) {
      return x;
    } else {
      return parent[x] = root_of(parent[x]);
    }
  }

  void unite(long long x, long long y) {
    long long rx = root_of(x);
    long long ry = root_of(y);
    if (rx == ry) {
      edge_count[rx]++;
      return;
    } else if (rank[rx] < rank[ry]) {
      parent[rx] = ry;
      size[ry] += size[rx];
      edge_count[ry] += edge_count[rx] + 1;
    } else {
      parent[ry] = rx;
      size[rx] += size[ry];
      if (rank[rx] == rank[ry])
        rank[rx]++;
      edge_count[rx] += edge_count[ry] + 1;
    }
    return;
  }

  bool is_same(long long x, long long y) { return root_of(x) == root_of(y); }

  long long size_of(long long x) { return size[root_of(x)]; }
  bool is_cycle(long long x) {
    return edge_count[root_of(x)] >= size[root_of(x)];
  }
};
} // namespace comavius::competitive

namespace comavius::competitive { // get_primes

std::vector<long long> get_primes(long long n) {
  std::vector<bool> is_prime(n + 1, true);
  std::vector<long long> primes;
  is_prime[0] = false;
  is_prime[1] = false;
  for (long long i = 2; i <= n; i++) {
    if (is_prime[i]) {
      primes.push_back(i);
      for (long long j = 2 * i; j <= n; j += i) {
        is_prime[j] = false;
      }
    }
  }
  return primes;
}
} // namespace comavius::competitive

namespace comavius::competitive { // fast pow (repeated squaring)

template <typename T> T fast_pow(T base, T neutral, long long exponent) {
  T ans = neutral;
  while (exponent > 0) {
    if (exponent % 2 == 1) {
      ans = ans * base;
    }
    base = base * base;
    exponent /= 2;
  }
  return ans;
}
} // namespace comavius::competitive

namespace comavius::competitive { // chmax/chmin

template <typename T> void chmax(T &a, T b) { a = std::max(a, b); }

template <typename T> void chmin(T &a, T b) { a = std::min(a, b); }

} // namespace comavius::competitive

namespace comavius::competitive { // Print(stdout, stderr)
template <typename T>
concept natively_printable = requires(T t) {
  { std::cout << t } -> std::same_as<std::ostream &>;
};
template <typename IteratableT, typename ElementT>
concept iteratable = requires(IteratableT t) {
  { t.begin() } -> std::same_as<typename IteratableT::iterator>;
  { t.end() } -> std::same_as<typename IteratableT::iterator>;
  { *t.begin() } -> std::same_as<ElementT>;
};
template <natively_printable T>
void internal_print(std::ostream &stream, T &s) {
  stream << s;
}
template <natively_printable ElementT, iteratable<ElementT> T>
void internal_print(std::ostream &stream, T &s) {
  for (auto it = s.begin(); it != s.end(); ++it) {
    if (it != s.begin())
      stream << " ";
    internal_print(stream, *it);
  }
}
template <typename GrandChildElementT, iteratable<GrandChildElementT> ChildT,
          iteratable<ChildT> T>
void internal_print(std::ostream &stream, T &s) {
  for (auto it = s.begin(); it != s.end(); ++it) {
    if (it != s.begin())
      stream << "\n";
    internal_print(stream, *it);
  }
}

// color enum-class
enum class Color { GREEN, RED, DEFAULT };

// ansi code color
std::string get_ansi_color(Color color) {
  if (IS_TEST_ENVIROMENT) {
    std::string ansi_code;
    switch (color) {
    case Color::RED:
      ansi_code = "\033[31m\033[1m";
      break;
    case Color::GREEN:
      ansi_code = "\033[32m\033[1m";
      break;
    case Color::DEFAULT:
      ansi_code = "\033[0m";
      break;
    }
    return ansi_code;
  } else {
    return "";
  }
}

template <typename T> void println(T t) {
  internal_print(std::cout, t);
  std::cout << "\n";
}
template <typename T> void println(T begin, T end) {
  print(begin, end);
  std::cout << "\n";
}
// yes or no
void yneos(bool a) {
  if (a) {
    println("Yes");
  } else {
    println("No");
  }
}
#pragma endregion // Print to stdout

#pragma region // ePrint to stderr
// default color(Color::CYAN)
template <typename T> void errprint(T t) {
  if (IS_TEST_ENVIROMENT) {
    std::cerr << get_ansi_color(Color::RED) << generate_string(t)
              << get_ansi_color(Color::DEFAULT);
  }
}
// set color
template <typename T> void errprint(T t, Color color) {
  if (IS_TEST_ENVIROMENT) {
    std::cerr << get_ansi_color(color) << generate_string(t)
              << get_ansi_color(Color::DEFAULT);
  }
}
// print"ln"
template <typename T> void errprintln(T t) {
  if (IS_TEST_ENVIROMENT) {
    errprint(t);
    std::cerr << "\n";
  }
}
template <typename T> void errprintln(T t, Color color) {
  if (IS_TEST_ENVIROMENT) {
    errprint(t, color);
    std::cerr << "\n";
  }
}
// print"ln" with iterator range
template <typename T> void errprintln(T begin, T end) {
  if (IS_TEST_ENVIROMENT) {
    errprint(begin, end);
    std::cerr << "\n";
  }
}
template <typename T> void errprintln(T begin, T end, Color color) {
  if (IS_TEST_ENVIROMENT) {
    errprint(begin, end, color);
    std::cerr << "\n";
  }
}
#pragma endregion // ePrint to stderr

} // namespace comavius::competitive

namespace comavius::competitive { // initial settings
void initial_settings() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cout << std::setprecision(15);
  std::cerr << std::setprecision(15);
}
} // namespace comavius::competitive

#pragma region // Read macro
#define GET_1_ARG(TYPE, ARG)                                                   \
  ;                                                                            \
  TYPE ARG;                                                                    \
  std::cin >> ARG;
#define GET_2_ARG(TYPE, ARG, ...)                                              \
  GET_1_ARG(TYPE, ARG) GET_1_ARG(TYPE, __VA_ARGS__)
#define GET_3_ARG(TYPE, ARG, ...)                                              \
  GET_1_ARG(TYPE, ARG) GET_2_ARG(TYPE, __VA_ARGS__)
#define GET_4_ARG(TYPE, ARG, ...)                                              \
  GET_1_ARG(TYPE, ARG) GET_3_ARG(TYPE, __VA_ARGS__)
#define GET_5_ARG(TYPE, ARG, ...)                                              \
  GET_1_ARG(TYPE, ARG) GET_4_ARG(TYPE, __VA_ARGS__)
#define GET_6_ARG(TYPE, ARG, ...)                                              \
  GET_1_ARG(TYPE, ARG) GET_5_ARG(TYPE, __VA_ARGS__)
#define GET_7_ARG(TYPE, ARG, ...)                                              \
  GET_1_ARG(TYPE, ARG) GET_6_ARG(TYPE, __VA_ARGS__)
#define GET_8_ARG(TYPE, ARG, ...)                                              \
  GET_1_ARG(TYPE, ARG) GET_7_ARG(TYPE, __VA_ARGS__)
#define GET_9_ARG(TYPE, ARG, ...)                                              \
  GET_1_ARG(TYPE, ARG) GET_8_ARG(TYPE, __VA_ARGS__)
#define GET_10_ARG(TYPE, ARG, ...)                                             \
  GET_1_ARG(TYPE, ARG) GET_9_ARG(TYPE, __VA_ARGS__)

#define GET_MACRO(_1, _2, _3, _4, _5, _6, _7, _8, _9, _10, NAME, ...) NAME
#define read(TYPE, ...)                                                        \
  GET_MACRO(__VA_ARGS__, GET_10_ARG, GET_9_ARG, GET_8_ARG, GET_7_ARG,          \
            GET_6_ARG, GET_5_ARG, GET_4_ARG, GET_3_ARG, GET_2_ARG,             \
            GET_1_ARG)(TYPE, __VA_ARGS__)

#define readv(TYPE, NAME, SIZE)                                                \
  std::vector<TYPE> NAME(SIZE);                                                \
  for (long long i = 0; i < SIZE; i++)                                         \
    std::cin >> NAME[i];
#define readvv(TYPE, NAME, H, W)                                               \
  std::vector<std::vector<TYPE>> NAME(H, std::vector<TYPE>(W));                \
  for (long long i = 0; i < H; i++)                                            \
    for (long long j = 0; j < W; j++)                                          \
      std::cin >> NAME[i][j];
#pragma endregion // Read macro

#pragma region // Other macro
#define rep(i, n) for (ll i = 0; i < n; i++)
#define reps(i, start, goal, diff) for (ll i = start; i != goal; i += diff)
#define all(a) a.begin(), a.end()
//    #define chmax(a, b) a = std::max(a, b)
//    #define chmin(a, b) a = std::min(a, b)
#pragma endregion // Other macro

#pragma region // namespace expansion
using namespace std;
using namespace comavius::competitive;
#pragma endregion // namespace expansion

#pragma endregion // comavius::competitive library

#include <atcoder/all>
using namespace atcoder;

#define F first
#define S second

ll op(ll l, ll r) { return l + r; }
ll e() { return 0; }

ll op2(ll l, ll r) { return max(l, r); }

int main() {
  read(ll, n, q);
  readv(ll, a, n);
  priority_queue<pair<pll, ll>, vector<pair<pll, ll>>, greater<pair<pll, ll>>>
      rls;
  rep(i, q) {
    read(ll, l, r);
    l--;
    rls.push({{r, l}, i});
  };
  vll ans(q);
  lazy_segtree<ll, op, e, ll, op, op, e> seg(n);
  segtree<ll, op2, e> seg2(a);
  rep(i, n + 1) {
    while (rls.size()) {
      if (rls.top().F.F == i) {
        auto [rl, index] = rls.top();
        rls.pop();
        auto [r, l] = rl;
        ans[index] = r - l - seg.get(l);
        // cerr << "query: " << index << " " << l << "\n";
      } else {
        break;
      }
    }
    if (i != n) {

      ll left = -1, right = i;
      while (right - left > 1) {
        ll mid = (right + left) / 2;
        if (seg2.prod(mid, i) > a[i]) {
          left = mid;
        } else {
          right = mid;
        }
      }
      seg.apply(right, i + 1, 1);
      //  cerr << "update: " << right << " " << i + 1 << "\n";
    }
  }
  rep(i, q) { cout << ans[i] << "\n"; }
}
0