結果
問題 | No.3017 交互浴 |
ユーザー |
|
提出日時 | 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 |
ソースコード
#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 longtemplate<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;}}