結果
| 問題 |
No.3305 Shift Sort
|
| コンテスト | |
| ユーザー |
|
| 提出日時 | 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 |
ソースコード
#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"; }
}