結果
問題 | No.284 門松と魔法(2) |
ユーザー |
![]() |
提出日時 | 2016-03-18 12:11:14 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 3,978 ms / 5,000 ms |
コード長 | 7,090 bytes |
コンパイル時間 | 1,813 ms |
コンパイル使用メモリ | 177,988 KB |
実行使用メモリ | 98,320 KB |
最終ジャッジ日時 | 2024-10-01 09:05:40 |
合計ジャッジ時間 | 32,035 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 40 |
ソースコード
#include<bits/stdc++.h>using namespace std;#define SEG_TREE_SIZE 500000#define NONE -1#define DEBUG if(0)typedef long long LL;#define cp(x) x=o.x#define INF 100010struct INIT{INIT(){ios::sync_with_stdio(false);cin.tie(0);}}init;vector<bool> used(SEG_TREE_SIZE,true);struct V{int id,v,prev;V(int id,int v,int prev):id(id),v(v),prev(prev){}void print(){printf("(id=%d,v=%d,prev=%d)\n",id,v,prev);}};class ND{public:pair<V,V> fs;ND():fs(V(0,-1,INF),V(0,-1,INF+1)){};ND(int id):fs(V(id,0,INF),V(id,0,INF+1)){};ND& copy(const ND& o){cp(fs);return *this;}ND& operator=(const ND& o){return copy(o);}ND operator+(const ND& o){ND res;auto fupdate=[&](const V& v){if(res.fs.first.v<v.v){used[res.fs.first.prev]=true;res.fs.first=v;used[res.fs.first.prev]=false;}};auto supdate=[&](const V& v){if(used[v.prev]&&res.fs.second.v<v.v){res.fs.second=v;}};fupdate(fs.first);fupdate(fs.second);fupdate(o.fs.first);fupdate(o.fs.second);supdate(fs.first);supdate(fs.second);supdate(o.fs.first);supdate(o.fs.second);used[res.fs.first.prev]=true;return res;}};template <typename T>class node{public:int bg,ed,L,R;T val,add_val,lazy_val;bool val_update,add_update;node():bg(NONE),ed(NONE),L(NONE),R(NONE),val(),add_val(),lazy_val(),val_update(false),add_update(false){}node(int bg,int ed,int L,int R):bg(bg),ed(ed),L(L),R(R),val(),add_val(),lazy_val(),val_update(false),add_update(false){}node(int bg,int ed,int L,int R,T val):bg(bg),ed(ed),L(L),R(R),val(val),add_val(),lazy_val(),val_update(false),add_update(false){}node(int bg,int ed,int L,int R,T val,T add_val):bg(bg),ed(ed),L(L),R(R),val(val),add_val(add_val),lazy_val(),val_update(false),add_update(false){}void set(T v){val_update=true,lazy_val=v;}void add(T v){add_update=true,add_val=add_val+v;}void update_clear(){val_update=add_update=false,add_val=lazy_val=T();}//T get(){return val+(add_val+lazy_val)*len();}T get(){return val+add_val+lazy_val;}int len(){return ed-bg+1;}node& copy(const node& o){cp(bg),cp(ed),cp(L),cp(R),cp(val),cp(add_val),cp(lazy_val),cp(val_update),cp(add_update);return *this;}node& operator=(const node& o){return copy(o);}bool isleaf(){return bg>=ed;}bool iscontain(int l,int r){return bg<=l&&r<=ed;}bool isequal(int l,int r){return l==bg&&r==ed;}void print(){printf("[%d-%d]updates(%d,%d)\n",bg,ed,(int)val_update,(int)add_update);get().print();}};node<LL> _seg_prepared_table[1];/**/template <typename T>inline T merge(node<T> &l,node<T> &r){return l.get()+r.get();}template <typename T>inline T merge(T &l,node<T> &r){return l+r.get();}template <typename T>class segtree{private:using NODE=node<T>;int begin,end;stack<int> st1,stL,stR,rollback;NODE *t;inline void lazy_update(NODE& now){if(now.isleaf())return;if(now.val_update){t[now.L].set(now.lazy_val);t[now.R].set(now.lazy_val);}if(now.add_update){t[now.L].add(now.add_val);t[now.R].add(now.add_val);}now.update_clear();}void all_update(){while(rollback.empty()==false){auto& now=t[rollback.top()];rollback.pop();if(!now.isleaf())now.val=merge(t[now.L],t[now.R]);}}public:segtree():begin(0),end(0),t(_seg_prepared_table){}segtree(int bg,int ed,NODE* t):begin(bg),end(ed),t(t){int sz=0;t[0]=NODE(bg,ed,sz+1,sz+2);sz+=2;st1.push(0);while(st1.empty()==false){int id=st1.top();st1.pop();rollback.push(id);auto& now=t[id];if(now.isleaf()){now.val=T(now.bg);continue;}int half=(now.bg+now.ed)/2;t[now.L]=NODE(now.bg,half,sz+1,sz+2);sz+=2;t[now.R]=NODE(half+1,now.ed,sz+1,sz+2);sz+=2;st1.push(now.L);st1.push(now.R);}all_update();}//遅延評価対応,値の書き換えvoid segment_set(int bg,int ed,T v){if(!t[0].iscontain(bg,ed)){printf("query=(segment_set,%d,%d) ERROR\n",bg,ed);exit(-1);}auto PUSH=[&](int id,int l,int r){st1.push(id),stL.push(l),stR.push(r);};auto POP=[&](int& id,int &l,int &r){id=st1.top(),l=stL.top(),r=stR.top();st1.pop(),stL.pop(),stR.pop();};PUSH(0,bg,ed);while(st1.empty()==false){int id,L,R;POP(id,L,R);rollback.push(id);auto &now=t[id];lazy_update(now);if(now.isequal(L,R)){now.set(v);continue;}if(t[now.L].iscontain(L,R))PUSH(now.L,L,R);else if(t[now.R].iscontain(L,R))PUSH(now.R,L,R);else {PUSH(now.L,L,t[now.L].ed);PUSH(now.R,t[now.R].bg,R);}}all_update();}void set(int pos,T v){segment_set(pos,pos,v);}void segment_add(int bg,int ed,T v){if(!t[0].iscontain(bg,ed)){printf("query=(segment_add,%d,%d) ERROR\n",bg,ed);exit(-1);}auto PUSH=[&](int id,int l,int r){st1.push(id),stL.push(l);stR.push(r);};auto POP=[&](int& id,int &l,int &r){id=st1.top(),l=stL.top(),r=stR.top();st1.pop(),stL.pop(),stR.pop();};PUSH(0,bg,ed);while(st1.empty()==false){int id,L,R;POP(id,L,R);rollback.push(id);auto &now=t[id];lazy_update(now);if(now.isequal(L,R)){now.add(v);continue;}if(t[now.L].iscontain(L,R))PUSH(now.L,L,R);else if(t[now.R].iscontain(L,R))PUSH(now.R,L,R);else {PUSH(now.L,L,t[now.L].ed);PUSH(now.R,t[now.R].bg,R);}}all_update();}T get(int bg,int ed){T res=T();auto PUSH=[&](int id,int l,int r){st1.push(id),stL.push(l),stR.push(r);};auto POP=[&](int& id,int &l,int &r){id=st1.top(),l=stL.top(),r=stR.top(),st1.pop(),stL.pop(),stR.pop();};PUSH(0,bg,ed);while(st1.empty()==false){int id,L,R;POP(id,L,R);rollback.push(id);auto &now=t[id];if(now.isequal(L,R)){res=merge(res,now);continue;}lazy_update(now);if(t[now.L].iscontain(L,R))PUSH(now.L,L,R);else if(t[now.R].iscontain(L,R))PUSH(now.R,L,R);else {PUSH(now.L,L,t[now.L].ed);PUSH(now.R,t[now.R].bg,R);}}all_update();return res;}};node<ND> _u[SEG_TREE_SIZE],_d[SEG_TREE_SIZE];int main(){int res=0;segtree<ND> up(0,INF+1,_u);segtree<ND> down(0,INF+1,_d);int N;cin>>N;vector<int> Q(N);map<int,int> m;for(auto& it : Q){cin>>it;m[it]=0;}{int t=2;for(auto& it : m)it.second=t++;}for(auto& it : Q){int h=m[it];ND U,D;{auto u=up.get(h+1,INF-2);if(u.fs.first.prev!=h)U.fs.first=u.fs.first;else U.fs.first=u.fs.second;u=up.get(U.fs.first.id+1,INF-1);if(U.fs.first.id!=h+1)u=u+up.get(h+1,U.fs.first.id-1);if(u.fs.first.prev!=h)U.fs.second=u.fs.first;else U.fs.second=u.fs.second;U.fs.first.v++;U.fs.second.v++;U.fs.first.prev=U.fs.first.id;U.fs.second.prev=U.fs.second.id;U.fs.first.id=U.fs.second.id=h;}{auto d=down.get(1,h-1);if(d.fs.first.prev!=h)D.fs.first=d.fs.first;else D.fs.first=d.fs.second;d=down.get(0,D.fs.first.id-1);if(D.fs.first.id!=h-1)d=d+down.get(D.fs.first.id+1,h-1);if(d.fs.first.prev!=h)D.fs.second=d.fs.first;else D.fs.second=d.fs.second;D.fs.first.v++;D.fs.second.v++;D.fs.first.prev=D.fs.first.id;D.fs.second.prev=D.fs.second.id;D.fs.first.id=D.fs.second.id=h;}down.set(h,U);up.set(h,D);res=max(res,U.fs.first.v);res=max(res,D.fs.first.v);}if(res<3)cout<<0<<endl;else cout<<res<<endl;}