結果

問題 No.2333 Slime Structure
ユーザー dyktr_06
提出日時 2023-05-05 19:38:53
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 371 ms / 3,000 ms
コード長 4,229 bytes
コンパイル時間 2,198 ms
コンパイル使用メモリ 217,784 KB
最終ジャッジ日時 2025-02-12 17:20:03
ジャッジサーバーID
(参考情報)
judge1 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 31
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
template <typename X>
struct SegTree{
using FX = function<X(X, X)>; // X•X -> X
int n;
FX fx;
const X ex;
vector<X> dat;
SegTree(int n_, FX fx_, X ex_) : n(), fx(fx_), ex(ex_){
int x = 1;
while(n_ > x){
x *= 2;
}
n = x;
dat.assign(n * 2, ex);
}
X get(int i){
return dat[i + n];
}
void set(int i, X x){ dat[i + n] = x; }
void build(){
for(int k = n - 1; k >= 1; k--) dat[k] = fx(dat[k * 2], dat[k * 2 + 1]);
}
void update(int i, X x){
i += n;
dat[i] = x;
while(i > 0){
i >>= 1; // parent
dat[i] = fx(dat[i * 2], dat[i * 2 + 1]);
}
}
X query(int a, int b){
X vl = ex;
X vr = ex;
int l = a + n;
int r = b + n;
while(l < r){
if(l & 1) vl = fx(vl, dat[l++]);
if(r & 1) vr = fx(dat[--r], vr);
l >>= 1;
r >>= 1;
}
return fx(vl, vr);
}
};
const long long INF = 1LL << 40;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q; cin >> n;
vector<long long> a(n), b(n);
for(int i = 0; i < n; i++){
cin >> a[i] >> b[i];
}
vector<long long> sum(n + 1), sum2(n + 1);
for(int i = 0; i < n; i++){
sum[i + 1] = sum[i] + b[i];
}
sum2 = sum;
cin >> q;
vector<tuple<int, long long, long long>> query(q);
vector<int> check;
for(int i = 0; i < q; i++){
int t;
long long x, y; cin >> t >> x >> y;
query[i] = {t, x, y};
if(t == 1){
sum2.push_back(x - 1);
sum2.push_back(x);
}
}
sort(sum2.begin(), sum2.end());
sum2.erase(unique(sum2.begin(), sum2.end()), sum2.end());
using T = tuple<long long, long long, long long, long long>;
auto fx = [](T x, T y) -> T {
auto [all1, left1, right1, res1] = x;
auto [all2, left2, right2, res2] = y;
return {all1 + all2, max(left1, all1 + left2), max(right2, all2 + right1), max({res1, res2, right1 + left2})};
};
int m = sum2.size() - 1;
SegTree<T> seg(m, fx, T(0, -INF, -INF, -INF));
for(int i = 1; i <= m; i++){
auto iter = lower_bound(sum.begin(), sum.end(), sum2[i]);
int k = (iter - sum.begin()) - 1;
int siz = sum2[i] - sum2[i - 1];
if(a[k] < 0){
seg.update(i - 1, T(a[k] * siz, a[k], a[k], a[k]));
}else{
seg.update(i - 1, T(a[k] * siz, a[k] * siz, a[k] * siz, a[k] * siz));
}
}
for(int i = 0; i < q; i++){
auto [t, x, y] = query[i];
if(t == 1){
x--;
int k = upper_bound(sum2.begin(), sum2.end(), x) - sum2.begin(); k--;
seg.update(k, T(y, y, y, y));
}else{
x--;
int k1 = upper_bound(sum2.begin(), sum2.end(), x) - sum2.begin(); k1--;
int k2 = upper_bound(sum2.begin(), sum2.end(), y - 1) - sum2.begin(); k2--;
if(k1 == k2){
int v = get<0>(seg.get(k1)) / (sum2[k1 + 1] - sum2[k1]);
if(v < 0){
cout << v << endl;
}else{
cout << v * (y - x) << endl;
}
}else{
int l = k1 + 1, r = k2;
T left, right;
long long v1 = get<0>(seg.get(k1)) / (sum2[k1 + 1] - sum2[k1]);
long long s1 = v1 * (sum2[k1 + 1] - x);
if(v1 < 0){
left = T(s1, v1, v1, v1);
}else{
left = T(s1, s1, s1, s1);
}
long long v2 = get<0>(seg.get(k2)) / (sum2[k2 + 1] - sum2[k2]);
long long s2 = v2 * (y - sum2[k2]);
if(v2 < 0){
right = T(s2, v2, v2, v2);
}else{
right = T(s2, s2, s2, s2);
}
T ans = left;
ans = fx(ans, seg.query(l, r));
ans = fx(ans, right);
cout << get<3>(ans) << endl;
}
}
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0