結果

問題 No.3017 交互浴
ユーザー nouka28nouka28
提出日時 2025-01-25 13:14:50
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,080 ms / 2,000 ms
コード長 5,774 bytes
コンパイル時間 6,192 ms
コンパイル使用メモリ 335,596 KB
実行使用メモリ 217,984 KB
最終ジャッジ日時 2025-01-25 22:40:42
合計ジャッジ時間 56,319 ms
ジャッジサーバーID
(参考情報)
judge10 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 1
other AC * 55
権限があれば一括ダウンロードができます

ソースコード

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

#include<bits/stdc++.h>
using namespace std;
#include<atcoder/all>
using namespace atcoder;
using mint=atcoder::modint998244353;
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
// #define int long long
template<class S,S (*op)(S,S),S (*e)(),class F,S (*mapping)(F,S,int),F (*composition)(F,F),F (*id)()>
class dynamic_lazy_segtree{
public:
dynamic_lazy_segtree(int n):n(n){root=new node(e(),id(),n);}
void set(int p,S x){
assert(p<n);
set(root,0,n,p,x);
}
S get(int p)const{
assert(p<n);
return get(root,0,n,p);
}
void apply(int l,int r,F f){
assert(0<=l&&l<=r&&r<=n);
apply(root,0,n,l,r,f);
}
S prod(int l,int r)const{
assert(0<=l&&l<=r&&r<=n);
return prod(root,0,n,l,r);
}
S all_prod()const{return prod(0,n);}
template<bool (*f)(S)> int max_right(int l)const{
return max_right(l,[](S x){return f(x);});
}
template<class G> int max_right(int l,const G& f)const{
assert(l<=n);
S product=e();
assert(f(product));
return max_right(root,0,n,l,f,product);
}
template<bool (*f)(S)> int min_left(int r)const{
return min_left(r,[](S x){return f(x);});
}
template<class G> int min_left(int r,const G& f)const{
assert(r<=n);
S product=e();
assert(f(product));
return min_left(root,0,n,r,f,product);
}
void dump(){
dump(root,0,n);cout<<endl;
}
private:
struct node{
S value;
F lazy,lazy_acc;
node *left,*right;
node(S value=e(),F lazy=id(),int l=0):value(value),lazy(lazy),lazy_acc(id()),left(nullptr),right(nullptr){eval(l);}
void update(int l,int r){
int m=(l+r)>>1;
value=op(left?left->value:mapping(lazy_acc,e(),m-l),right?right->value:mapping(lazy_acc,e(),r-m));
return;
}
void eval(int l){
value=mapping(lazy,value,l);
if(left)left->lazy=composition(lazy,left->lazy);
if(right)right->lazy=composition(lazy,right->lazy);
lazy_acc=composition(lazy,lazy_acc);
lazy=id();
return;
}
};
int n;
node* root;
void set(node* t,int l,int r,int p,S x)const{
t->eval(r-l);
int m=(l+r)>>1;
if(l==p&&r==p+1){
t->value=x;
return;
}else{
if(!t->left)t->left=new node(e(),t->lazy_acc,m-l);
if(!t->right)t->right=new node(e(),t->lazy_acc,r-m);
}
if(p<m){
set(t->left,l,m,p,x);
}else{
set(t->right,m,r,p,x);
}
t->update(l,r);
}
S get(node* t,int l,int r,int p)const{
t->eval(r-l);
if(l==p&&r==p+1){
return t->value;
}
int m=(l+r)>>1;
if(p<m)return t->left?get(t->left,l,m,p):mapping(t->lazy_acc,e(),1);
else return t->right?get(t->right,m,r,p):mapping(t->lazy_acc,e(),1);
}
void apply(node* t,int l,int r,int a,int b,F f)const{
t->eval(r-l);
if(b<=l||r<=a)return;
if(a<=l&&r<=b){
t->lazy=composition(f,t->lazy);
t->eval(r-l);
return;
}
int m=(l+r)>>1;
if(!t->left){
t->left=new node(e(),t->lazy_acc,m-l);
}
if(!t->right){
t->right=new node(e(),t->lazy_acc,r-m);
}
apply(t->left,l,m,a,b,f);
apply(t->right,m,r,a,b,f);
t->update(l,r);
}
S prod(node* t,int l,int r,int a,int b)const{
t->eval(r-l);
if(b<=l||r<=a)return e();
if(a<=l&&r<=b)return t->value;
int m=(l+r)>>1;
return op(t->left?prod(t->left,l,m,a,b):mapping(t->lazy_acc,e(),max({0,min(m,b)-max(l,a)})),t->right?prod(t->right,m,r,a,b):mapping(t
            ->lazy_acc,e(),max({0,min(r,b)-max(m,a)})));
}
template<class G>
int max_right(node* t,int l,int r,int L,const G& f,S &product)const{
t->eval(r-l);
if(r<=L)return r;
if(!f(product))return l;
if(f(op(product,prod(t,l,r,L,n))))return r;
int m=(l+r)>>1;
int res=t->left?max_right(t->left,l,m,L,f,product):m;
if(res!=m)return res;
product=op(product,t->left?prod(t->left,l,m,L,n):mapping(t->lazy_acc,e(),m-l));
if(!f(product))return l;
return t->right?max_right(t->right,m,r,L,f,product):r-1;
}
template<class G>
int min_left(node* t,int l,int r,int R,const G& f,S &product)const{
t->eval(r-l);
if(l>=R)return l;
if(!f(product))return r;
if(f(op(product,prod(t,l,r,0,R))))return l;
int m=(l+r)>>1;
int res=t->right?min_left(t->right,m,r,R,f,product):m;
if(res!=m)return res;
product=op(product,t->right?prod(t->right,m,r,0,r):mapping(t->lazy_acc,e(),r-m));
if(!f(product))return r;
return t->left?min_left(t->left,l,m,R,f,product):l+1;
}
void dump(node* t,int l,int r){
t->eval(r-l);
cout<<"("<<l<<" "<<r<<" "<<t->value<<" "<<t->lazy_acc<<"),";
int m=(l+r)>>1;
if(t->left)dump(t->left,l,m);
if(t->right)dump(t->right,m,r);
}
};
using P=pair<int,int>;
P op(P a,P b){
return {a.first+b.first,a.second+b.second};
}
P e(){
return {0,0};
}
P mapping(int f,P x,int len){
if(f==-1)return x;
if(f==0)return {len,0};
else return {0,len};
}
int composition(int f,int g){
if(f==-1)return g;
else return f;
}
int id(){return -1;}
signed main(){
int N;cin>>N;
dynamic_lazy_segtree<P,op,e,int,mapping,composition,id> seg(2e9);
for(int i=0;i<N;i++){
int h;cin>>h;
seg.apply(0,h,i%2);
P ans=seg.all_prod();
cout<<ans.first<<endl;
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0