結果
問題 | No.876 Range Compress Query |
ユーザー | WALLEatCoder |
提出日時 | 2019-09-06 23:07:02 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 305 ms / 2,000 ms |
コード長 | 3,873 bytes |
コンパイル時間 | 2,218 ms |
コンパイル使用メモリ | 67,140 KB |
実行使用メモリ | 16,652 KB |
最終ジャッジ日時 | 2023-09-07 02:22:34 |
合計ジャッジ時間 | 4,591 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge14 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,380 KB |
testcase_01 | AC | 3 ms
4,376 KB |
testcase_02 | AC | 2 ms
4,376 KB |
testcase_03 | AC | 3 ms
4,376 KB |
testcase_04 | AC | 2 ms
4,376 KB |
testcase_05 | AC | 2 ms
4,376 KB |
testcase_06 | AC | 3 ms
4,376 KB |
testcase_07 | AC | 3 ms
4,376 KB |
testcase_08 | AC | 3 ms
4,376 KB |
testcase_09 | AC | 3 ms
4,380 KB |
testcase_10 | AC | 3 ms
4,380 KB |
testcase_11 | AC | 299 ms
15,040 KB |
testcase_12 | AC | 250 ms
14,444 KB |
testcase_13 | AC | 257 ms
14,928 KB |
testcase_14 | AC | 301 ms
15,188 KB |
testcase_15 | AC | 210 ms
15,684 KB |
testcase_16 | AC | 300 ms
16,652 KB |
testcase_17 | AC | 293 ms
16,232 KB |
testcase_18 | AC | 305 ms
16,504 KB |
ソースコード
#include<vector> #include<iostream> using namespace std; #define df 0 typedef long int li; /// Segment Tree (prototype) /// template<typename Monoid,typename Action> class lazySegTree{ int n; vector<pair<Action,Monoid>> node; public: int parent(int a){return (a-1)/2;} int left(int a) {return (a*2+1);} int right(int a) {return (a*2+2);} int leaf(int a){return (a+n-1);} lazySegTree(vector<Monoid> v); lazySegTree(int k); void eval(int k,int l,int r); void update(Action g,int a,int b,int i,int l,int ); void update(Action g,int a,int b){return update(g,a,b,0,0,n);} Monoid find(int a,int b,int i,int l,int r); Monoid find(int a,int b){return find(a,b,0,0,n);} void print(){ for(int i=0;i<2*n-1;i++){ printf("%d: (",i); node.at(i).first.print(); printf("."); node.at(i).second.print(); printf(")\n"); } } }; /// Segment Tree /// struct mono{ li l; li r; int cnt; mono(){l=r=-1;cnt=0;} mono(li a){l=r=a; cnt=0;} mono(li ll,li rr,li count){l=ll;r=rr;cnt=count;} mono operator+(mono m){ if(r<0)return m; if(m.r<0)return *this; int s=cnt+m.cnt; if(r!=m.l)s++; return (mono){l,m.r,s}; } void print(){printf("(%ld,%ld;%d) ",l,r,cnt);} }; struct act{ li x; act(){x=0;} act(li a){x=a;} li get(){return x;} act operator*(act g) {return x+g.x;} mono operator*(mono m){ return (mono){m.l+x,m.r+x,m.cnt}; } act operator^(int k){ return *this;} void print(){printf("%ld",x);} }; int main(){ if(df) printf("*debug mode*\n"); int n,q; cin >>n >>q; vector<mono> a; for(int i=0;i<n;i++){ int x; cin >>x; a.push_back((mono)x); } lazySegTree<mono,act> lst(a); for(int i=0;i<q;i++){ int flag; cin >>flag; if(flag==1){ li l,r,x; cin >>l >>r >>x;l--; lst.update(x,l,r); }else{ li l,r; cin >>l >>r; l--; if(df)printf("find [%d,%d)\n",l,r); mono m=lst.find(l,r); printf("%d\n",m.cnt+1); } if(df)lst.print(); } } /// Segment Tree (main) /// template<typename Monoid,typename Action> lazySegTree<Monoid,Action>::lazySegTree(vector<Monoid> v){ int sz=v.size(); Action g; n=1; while(n<sz)n*=2; node.resize(2*n-1); for(int i=0;i<v.size();i++){ node.at(i+n-1)=make_pair(g,v.at(i)); } for(int i=n-2;i>=0;i--){ node.at(i).second=(node.at(left(i)).second)+(node.at(right(i)).second); } } template<typename Monoid,typename Action> lazySegTree<Monoid,Action>::lazySegTree(int k){ int sz=k; n=1; while(n<sz)n*=2; node.resize(2*n-1); } template<typename Monoid,typename Action> void lazySegTree<Monoid,Action>::eval(int i,int l,int r){ Action& g=node.at(i).first; node.at(i).second=(g^(r-l+1))*(node.at(i).second); if(r-l>1){ node.at(left(i)).first=g*node.at(left(i)).first; node.at(right(i)).first=g*node.at(right(i)).first; } Action g0; g=g0; } template<typename Monoid,typename Action> void lazySegTree<Monoid,Action>::update(Action g,int a,int b, int i,int l,int r){ eval(i,l,r); if(r<=a || b<=l)return; if(a<=l && r<=b){ node.at(i).first=g*(node.at(i).first); eval(i,l,r); return; } update(g,a,b,left(i) ,l,(l+r)/2); update(g,a,b,right(i),(l+r)/2,r); node.at(i).second=node.at(left(i)).second+node.at(right(i)).second; } template<typename Monoid,typename Action> Monoid lazySegTree<Monoid,Action>::find(int a,int b,int i,int l,int r){ Monoid x; if(df)printf("[%d,%d)",l,r); if(r<=a || b<=l){ return x; } eval(i,l,r); if(a<=l && r<=b){ if(df){ node.at(i).second.print(); printf("\n"); } return node.at(i).second; } Monoid m1=find(a,b,this->left(i) ,l,(l+r)/2); Monoid m2=find(a,b,this->right(i),(l+r)/2,r); x=m1+m2; if(df){ m1.print();cout<<"+"; m2.print(); cout <<"="; x.print(); } return x; } /// Segment Tree /// /// confirm df==0 ///