結果
| 問題 |
No.3314 Library Rearrangement
|
| コンテスト | |
| ユーザー |
 noya2
|
| 提出日時 | 2025-10-24 22:42:51 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 799 ms / 3,000 ms |
| コード長 | 23,119 bytes |
| コンパイル時間 | 3,537 ms |
| コンパイル使用メモリ | 305,832 KB |
| 実行使用メモリ | 12,352 KB |
| 最終ジャッジ日時 | 2025-10-24 22:43:17 |
| 合計ジャッジ時間 | 25,003 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 39 |
ソースコード
#line 2 "/Users/noya2/Desktop/Noya2_library/template/template.hpp"
using namespace std;
#include<bits/stdc++.h>
#line 1 "/Users/noya2/Desktop/Noya2_library/template/inout_old.hpp"
namespace noya2 {
template <typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &p){
os << p.first << " " << p.second;
return os;
}
template <typename T, typename U>
istream &operator>>(istream &is, pair<T, U> &p){
is >> p.first >> p.second;
return is;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v){
int s = (int)v.size();
for (int i = 0; i < s; i++) os << (i ? " " : "") << v[i];
return os;
}
template <typename T>
istream &operator>>(istream &is, vector<T> &v){
for (auto &x : v) is >> x;
return is;
}
void in() {}
template <typename T, class... U>
void in(T &t, U &...u){
cin >> t;
in(u...);
}
void out() { cout << "\n"; }
template <typename T, class... U, char sep = ' '>
void out(const T &t, const U &...u){
cout << t;
if (sizeof...(u)) cout << sep;
out(u...);
}
template<typename T>
void out(const vector<vector<T>> &vv){
int s = (int)vv.size();
for (int i = 0; i < s; i++) out(vv[i]);
}
struct IoSetup {
IoSetup(){
cin.tie(nullptr);
ios::sync_with_stdio(false);
cout << fixed << setprecision(15);
cerr << fixed << setprecision(7);
}
} iosetup_noya2;
} // namespace noya2
#line 1 "/Users/noya2/Desktop/Noya2_library/template/const.hpp"
namespace noya2{
const int iinf = 1'000'000'007;
const long long linf = 2'000'000'000'000'000'000LL;
const long long mod998 = 998244353;
const long long mod107 = 1000000007;
const long double pi = 3.14159265358979323;
const vector<int> dx = {0,1,0,-1,1,1,-1,-1};
const vector<int> dy = {1,0,-1,0,1,-1,-1,1};
const string ALP = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const string alp = "abcdefghijklmnopqrstuvwxyz";
const string NUM = "0123456789";
void yes(){ cout << "Yes\n"; }
void no(){ cout << "No\n"; }
void YES(){ cout << "YES\n"; }
void NO(){ cout << "NO\n"; }
void yn(bool t){ t ? yes() : no(); }
void YN(bool t){ t ? YES() : NO(); }
} // namespace noya2
#line 2 "/Users/noya2/Desktop/Noya2_library/template/utils.hpp"
#line 6 "/Users/noya2/Desktop/Noya2_library/template/utils.hpp"
namespace noya2{
unsigned long long inner_binary_gcd(unsigned long long a, unsigned long long b){
if (a == 0 || b == 0) return a + b;
int n = __builtin_ctzll(a); a >>= n;
int m = __builtin_ctzll(b); b >>= m;
while (a != b) {
int mm = __builtin_ctzll(a - b);
bool f = a > b;
unsigned long long c = f ? a : b;
b = f ? b : a;
a = (c - b) >> mm;
}
return a << std::min(n, m);
}
template<typename T> T gcd_fast(T a, T b){ return static_cast<T>(inner_binary_gcd(std::abs(a),std::abs(b))); }
long long sqrt_fast(long long n) {
if (n <= 0) return 0;
long long x = sqrt(n);
while ((x + 1) * (x + 1) <= n) x++;
while (x * x > n) x--;
return x;
}
template<typename T> T floor_div(const T n, const T d) {
assert(d != 0);
return n / d - static_cast<T>((n ^ d) < 0 && n % d != 0);
}
template<typename T> T ceil_div(const T n, const T d) {
assert(d != 0);
return n / d + static_cast<T>((n ^ d) >= 0 && n % d != 0);
}
template<typename T> void uniq(std::vector<T> &v){
std::sort(v.begin(),v.end());
v.erase(unique(v.begin(),v.end()),v.end());
}
template <typename T, typename U> inline bool chmin(T &x, U y) { return (y < x) ? (x = y, true) : false; }
template <typename T, typename U> inline bool chmax(T &x, U y) { return (x < y) ? (x = y, true) : false; }
template<typename T> inline bool range(T l, T x, T r){ return l <= x && x < r; }
} // namespace noya2
#line 8 "/Users/noya2/Desktop/Noya2_library/template/template.hpp"
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define repp(i,m,n) for (int i = (m); i < (int)(n); i++)
#define reb(i,n) for (int i = (int)(n-1); i >= 0; i--)
#define all(v) (v).begin(),(v).end()
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using pil = pair<int,ll>;
using pli = pair<ll,int>;
namespace noya2{
/* ~ (. _________ . /) */
}
using namespace noya2;
#line 2 "c.cpp"
// https://judge.yosupo.jp/submission/204482
namespace OY {
namespace SegBeat {
using size_type = uint32_t;
struct Ignore {};
template <typename Node>
struct Tree {
using node = Node;
struct DefaultGetter {
using value_type = decltype(std::declval<node>().get());
const value_type &operator()(node *x) const { return x->get(); }
};
mutable std::vector<node> m_sub;
size_type m_capacity, m_depth, m_size;
template <typename Modify>
static void _apply(node *sub, size_type i, Modify &&modify, size_type len) {
if (!node::map(modify, sub + i, len)) {
_pushdown(sub, i, len);
_apply(sub, i * 2, modify, len >> 1), _apply(sub, i * 2 + 1, modify, len >> 1);
_pushup(sub, i);
}
}
static void _pushdown(node *sub, size_type i, size_type len) { sub[i].pushdown(sub + i * 2, sub + (i * 2 + 1), len); }
static void _pushup(node *sub, size_type i) { sub[i].pushup(sub + (i * 2), sub + (i * 2 + 1)); }
static void _fetch(node *sub, size_type l, size_type r, size_type len) {
if (l == 1) return;
_fetch(sub, l >> 1, r >> 1, len << 1);
for (size_type i = l >> 1; i <= r >> 1; i++) _pushdown(sub, i, len);
}
Tree() = default;
template <typename InitMapping = Ignore>
Tree(size_type length, InitMapping mapping = InitMapping()) { resize(length, mapping); }
template <typename Iterator>
Tree(Iterator first, Iterator last) { reset(first, last); }
template <typename InitMapping>
void resize(size_type length, InitMapping mapping = InitMapping()) {
if (!(m_size = length)) return;
m_depth = std::bit_width(m_size - 1), m_capacity = 1 << m_depth;
m_sub.resize(m_capacity * 2);
node *sub = m_sub.data();
if constexpr (!std::is_same<InitMapping, Ignore>::value) {
for (size_type i = 0; i < m_size; i++) sub[m_capacity + i].set(mapping(i));
for (size_type len = m_capacity / 2, cnt = (m_size + 1) / 2, k = 2; len; len >>= 1, cnt = (cnt + 1) / 2, k <<= 1)
for (size_type i = len; i != len + cnt; i++) _pushup(sub, i);
}
}
template <typename Iterator>
void reset(Iterator first, Iterator last) {
resize(last - first, [&](size_type i) { return *(first + i); });
}
template <typename Modify>
void modify(size_type i, Modify &&modify) {
i += m_capacity;
node *sub = m_sub.data();
for (size_type d = m_depth, len = m_capacity; d; d--, len >>= 1) _pushdown(sub, i >> d, len);
modify(sub + i);
while (i >>= 1) _pushup(sub, i);
}
template <typename Modify>
void add(size_type i, Modify &&modify) {
i += m_capacity;
node *sub = m_sub.data();
for (size_type d = m_depth, len = m_capacity; d; d--, len >>= 1) _pushdown(sub, i >> d, len);
_apply(sub, i, modify, 1);
while (i >>= 1) _pushup(sub, i);
}
template <typename Modify>
void add(size_type left, size_type right, Modify &&modify) {
if (left == right) return add(left, modify);
left += m_capacity, right += m_capacity;
node *sub = m_sub.data();
size_type j = std::bit_width(left ^ right) - 1, len = m_capacity;
for (size_type d = m_depth; d > j; d--, len >>= 1) _pushdown(sub, left >> d, len);
for (size_type d = j; d; d--, len >>= 1) _pushdown(sub, left >> d, len), _pushdown(sub, right >> d, len);
_apply(sub, left, modify, 1), _apply(sub, right, modify, 1), len = 1;
while (left >> 1 < right >> 1) {
if (!(left & 1)) _apply(sub, left + 1, modify, len);
_pushup(sub, left >>= 1);
if (right & 1) _apply(sub, right - 1, modify, len);
_pushup(sub, right >>= 1);
len <<= 1;
}
while (left >>= 1) _pushup(sub, left);
}
template <typename Getter = DefaultGetter>
typename Getter::value_type query(size_type i) const {
i += m_capacity;
node *sub = m_sub.data();
for (size_type d = m_depth, len = m_capacity; d; d--, len >>= 1) _pushdown(sub, i >> d, len);
return Getter()(sub + i);
}
template <typename Getter>
typename Getter::value_type query(size_type left, size_type right) const {
if (left == right) return query<Getter>(left);
left += m_capacity, right += m_capacity;
node *sub = m_sub.data();
size_type j = std::bit_width(left ^ right) - 1, len = m_capacity;
for (size_type d = m_depth; d > j; d--, len >>= 1) _pushdown(sub, left >> d, len);
for (size_type d = j; d; d--, len >>= 1) _pushdown(sub, left >> d, len), _pushdown(sub, right >> d, len);
typename Getter::value_type resl = Getter()(sub + left), resr = Getter()(sub + right);
for (; left >> 1 != right >> 1; left >>= 1, right >>= 1) {
if (!(left & 1)) resl = Getter()(resl, Getter()(sub + (left ^ 1)));
if (right & 1) resr = Getter()(Getter()(sub + (right ^ 1)), resr);
}
return Getter()(resl, resr);
}
template <typename Callback>
void do_for_each(Callback &&call) {
node *sub = m_sub.data();
_fetch(sub, m_capacity, m_capacity + m_size - 1, 2);
for (size_type i = m_capacity, j = 0; j != m_size; i++, j++) call(sub + i);
}
};
template <typename Ostream, typename Node>
Ostream &operator<<(Ostream &out, const Tree<Node> &x) {
out << "[";
for (size_type i = 0; i < x.m_size; i++) {
if (i) out << ", ";
out << x.query(i);
}
return out << "]";
}
template <typename CountType, typename SumType, bool ChangeMin, bool ChangeMax, bool IsVoid>
struct ChminChmaxNodeBaseBase {
SumType m_sum;
CountType m_max_cnt, m_min_cnt;
};
template <typename CountType, typename SumType>
struct ChminChmaxNodeBaseBase<CountType, SumType, true, false, false> {
SumType m_sum;
CountType m_max_cnt;
};
template <typename CountType, typename SumType>
struct ChminChmaxNodeBaseBase<CountType, SumType, false, true, false> {
SumType m_sum;
CountType m_min_cnt;
};
template <typename CountType, typename SumType>
struct ChminChmaxNodeBaseBase<CountType, SumType, false, false, false> {
SumType m_sum;
};
template <typename CountType, bool ChangeMin, bool ChangeMax>
struct ChminChmaxNodeBaseBase<CountType, void, ChangeMin, ChangeMax, true> {
};
template <typename ValueType, typename CountType, typename SumType, bool ChangeMin, bool ChangeMax, bool ChangeAdd>
struct ChminChmaxNodeBase {
};
template <typename ValueType, typename CountType, typename SumType>
struct ChminChmaxNodeBase<ValueType, CountType, SumType, true, true, true> : ChminChmaxNodeBaseBase<CountType, SumType, true, true, std::is_void<SumType>::value> {
ValueType m_max1, m_max2, m_min1, m_min2, m_inc;
};
template <typename ValueType, typename CountType, typename SumType>
struct ChminChmaxNodeBase<ValueType, CountType, SumType, true, true, false> : ChminChmaxNodeBaseBase<CountType, SumType, true, true, std::is_void<SumType>::value> {
ValueType m_max1, m_max2, m_min1, m_min2;
};
template <typename ValueType, typename CountType, typename SumType>
struct ChminChmaxNodeBase<ValueType, CountType, SumType, true, false, true> : ChminChmaxNodeBaseBase<CountType, SumType, true, false, std::is_void<SumType>::value> {
ValueType m_max1, m_max2, m_inc;
};
template <typename ValueType, typename CountType, typename SumType>
struct ChminChmaxNodeBase<ValueType, CountType, SumType, true, false, false> : ChminChmaxNodeBaseBase<CountType, SumType, true, false, std::is_void<SumType>::value> {
ValueType m_max1, m_max2;
};
template <typename ValueType, typename CountType, typename SumType>
struct ChminChmaxNodeBase<ValueType, CountType, SumType, false, true, true> : ChminChmaxNodeBaseBase<CountType, SumType, false, true, std::is_void<SumType>::value> {
ValueType m_min1, m_min2, m_inc;
};
template <typename ValueType, typename CountType, typename SumType>
struct ChminChmaxNodeBase<ValueType, CountType, SumType, false, true, false> : ChminChmaxNodeBaseBase<CountType, SumType, false, true, std::is_void<SumType>::value> {
ValueType m_min1, m_min2;
};
template <typename ValueType, typename CountType, typename SumType, bool ChangeMin, bool ChangeMax, bool ChangeAdd, ValueType Min = std::numeric_limits<ValueType>::min() / 2, ValueType Max = std::numeric_limits<ValueType>::max() / 2>
struct ChminChmaxNode : ChminChmaxNodeBase<ValueType, CountType, SumType, ChangeMin, ChangeMax, ChangeAdd> {
static constexpr ValueType min = Min, max = Max;
using node_type = ChminChmaxNode<ValueType, CountType, SumType, ChangeMin, ChangeMax, ChangeAdd, Min, Max>;
struct Chmin {
ValueType m_chmin_by;
};
struct Chmax {
ValueType m_chmax_by;
};
struct Assign {
ValueType m_val;
};
struct Add {
ValueType m_add_by;
};
struct MinGetter {
using value_type = ValueType;
value_type operator()(node_type *x) const { return x->m_min1; }
value_type operator()(value_type x, value_type y) const { return std::min(x, y); }
};
struct MaxGetter {
using value_type = ValueType;
value_type operator()(node_type *x) const { return x->m_max1; }
value_type operator()(value_type x, value_type y) const { return std::max(x, y); }
};
struct SumGetter {
using value_type = SumType;
value_type operator()(node_type *x) const { return x->m_sum; }
value_type operator()(value_type x, value_type y) const { return x + y; }
};
static bool map(const Chmin &chmin, node_type *x, CountType len) {
if (x->m_max1 <= chmin.m_chmin_by) return true;
if (x->m_max2 < chmin.m_chmin_by) return x->chmin_by(chmin.m_chmin_by), true;
return false;
}
static bool map(const Chmax &chmax, node_type *x, CountType len) {
if (x->m_min1 >= chmax.m_chmax_by) return true;
if (x->m_min2 > chmax.m_chmax_by) return x->chmax_by(chmax.m_chmax_by), true;
return false;
}
static bool map(const Assign &assign, node_type *x, CountType len) { return x->m_min1 == x->m_max1 ? x->add_by(assign.m_val - x->m_max1, len), true : false; }
static bool map(const Add &inc, node_type *x, CountType len) { return x->add_by(inc.m_add_by, len), true; }
void set(ValueType val) {
if constexpr (!std::is_void<SumType>::value) this->m_sum = val;
if constexpr (ChangeMin) {
this->m_max1 = val, this->m_max2 = min;
if constexpr (!std::is_void<SumType>::value) this->m_max_cnt = 1;
}
if constexpr (ChangeMax) {
this->m_min1 = val, this->m_min2 = max;
if constexpr (!std::is_void<SumType>::value) this->m_min_cnt = 1;
}
}
const ValueType &get() const { return this->m_max1; }
void add_by(ValueType inc, CountType len) {
if constexpr (!std::is_void<SumType>::value) this->m_sum += SumType(inc) * len;
if constexpr (ChangeMin) {
this->m_max1 += inc;
if (this->m_max2 != min) this->m_max2 += inc;
}
if constexpr (ChangeMax) {
this->m_min1 += inc;
if (this->m_min2 != max) this->m_min2 += inc;
}
this->m_inc += inc;
}
void chmin_by(ValueType val) {
if constexpr (!std::is_void<SumType>::value) this->m_sum += SumType(val - this->m_max1) * this->m_max_cnt;
if constexpr (ChangeMax) {
if (this->m_min1 == this->m_max1) this->m_min1 = val;
if (this->m_min2 == this->m_max1) this->m_min2 = val;
}
this->m_max1 = val;
}
void chmax_by(ValueType val) {
if constexpr (!std::is_void<SumType>::value) this->m_sum += SumType(val - this->m_min1) * this->m_min_cnt;
if constexpr (ChangeMin) {
if (this->m_max1 == this->m_min1) this->m_max1 = val;
if (this->m_max2 == this->m_min1) this->m_max2 = val;
}
this->m_min1 = val;
}
void pushup(node_type *lchild, node_type *rchild) {
if constexpr (!std::is_void<SumType>::value) this->m_sum = lchild->m_sum + rchild->m_sum;
if constexpr (ChangeMin)
if (lchild->m_max1 == rchild->m_max1) {
this->m_max1 = lchild->m_max1;
this->m_max2 = std::max(lchild->m_max2, rchild->m_max2);
if constexpr (!std::is_void<SumType>::value) this->m_max_cnt = lchild->m_max_cnt + rchild->m_max_cnt;
} else if (lchild->m_max1 > rchild->m_max1) {
this->m_max1 = lchild->m_max1;
if constexpr (!std::is_void<SumType>::value) this->m_max_cnt = lchild->m_max_cnt;
this->m_max2 = std::max(lchild->m_max2, rchild->m_max1);
} else {
this->m_max1 = rchild->m_max1;
if constexpr (!std::is_void<SumType>::value) this->m_max_cnt = rchild->m_max_cnt;
this->m_max2 = std::max(lchild->m_max1, rchild->m_max2);
}
if constexpr (ChangeMax)
if (lchild->m_min1 == rchild->m_min1) {
this->m_min1 = lchild->m_min1;
this->m_min2 = std::min(lchild->m_min2, rchild->m_min2);
if constexpr (!std::is_void<SumType>::value) this->m_min_cnt = lchild->m_min_cnt + rchild->m_min_cnt;
} else if (lchild->m_min1 < rchild->m_min1) {
this->m_min1 = lchild->m_min1;
if constexpr (!std::is_void<SumType>::value) this->m_min_cnt = lchild->m_min_cnt;
this->m_min2 = std::min(lchild->m_min2, rchild->m_min1);
} else {
this->m_min1 = rchild->m_min1;
if constexpr (!std::is_void<SumType>::value) this->m_min_cnt = rchild->m_min_cnt;
this->m_min2 = std::min(lchild->m_min1, rchild->m_min2);
}
}
void pushdown(node_type *lchild, node_type *rchild, CountType len) {
if constexpr (ChangeAdd)
if (this->m_inc) {
lchild->add_by(this->m_inc, len >> 1);
rchild->add_by(this->m_inc, len >> 1);
this->m_inc = 0;
}
if constexpr (ChangeMin)
if (this->m_max1 < lchild->m_max1) lchild->chmin_by(this->m_max1);
if constexpr (ChangeMax)
if (this->m_min1 > lchild->m_min1) lchild->chmax_by(this->m_min1);
if constexpr (ChangeMin)
if (this->m_max1 < rchild->m_max1) rchild->chmin_by(this->m_max1);
if constexpr (ChangeMax)
if (this->m_min1 > rchild->m_min1) rchild->chmax_by(this->m_min1);
}
};
}
template <typename ValueType, typename CountType, typename SumType, bool ChangeMin, bool ChangeMax, bool ChangeAdd, ValueType Min = std::numeric_limits<ValueType>::min() / 2, ValueType Max = std::numeric_limits<ValueType>::max() / 2>
using ChminChmaxAddTree = SegBeat::Tree<SegBeat::ChminChmaxNode<ValueType, CountType, SumType, ChangeMin, ChangeMax, ChangeAdd, Min, Max>>;
}
void solve(){
int n, k, q; in(n,k,q);
vector<int> a(n); in(a);
vector<tuple<int,int,int>> upds(k);
rep(i,k){
int l, r; in(l,r); l--;
int x; in(x);
upds[i] = {l,r,x};
}
vector<tuple<int,int,ll>> qs(q);
rep(i,q){
int l, r; in(l,r); l--;
ll x; in(x);
qs[i] = {l,r,x};
}
vector<int> ls(q,-1), rs(q,k+1);
vector<int> ms(q);
vector<int> ids(q); iota(all(ids),0);
int many = 14;
while (many--){
rep(i,q){
ms[i] = (ls[i] + rs[i]) / 2;
}
ranges::sort(ids, {},[&](int i){
return ms[i];
});
OY::ChminChmaxAddTree<int64_t, int32_t, int64_t, true, true, true> seg(all(a));
using node = decltype(seg)::node;
int updr = 0;
for (int i : ids){
while (updr < ms[i]){
auto [l, r, x] = upds[updr++];
seg.add(l,r-1,node::Chmax{x});
}
auto [l, r, x] = qs[i];
if (seg.query<node::SumGetter>(l,r-1) >= x){
rs[i] = ms[i];
}
else {
ls[i] = ms[i];
}
}
}
rep(i,q){
int ans = rs[i];
if (ans == k+1){
ans = -1;
}
out(ans);
}
}
int main(){
int t = 1; //in(t);
while (t--) { solve(); }
}