結果

問題 No.284 門松と魔法(2)
ユーザー btkbtk
提出日時 2016-03-17 23:40:58
言語 C++11
(gcc 13.3.0)
結果
MLE  
実行時間 -
コード長 6,962 bytes
コンパイル時間 2,163 ms
コンパイル使用メモリ 172,844 KB
実行使用メモリ 814,512 KB
最終ジャッジ日時 2024-10-01 08:57:42
合計ジャッジ時間 5,621 ms
ジャッジサーバーID
(参考情報)
judge3 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other MLE * 1 -- * 39
権限があれば一括ダウンロードができます

ソースコード

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

#include<bits/stdc++.h>
using namespace std;
#define SEG_TREE_SIZE 5000000
#define NONE -1
#define DEBUG if(1)
typedef long long LL;
#define cp(x) x=o.x
#define INF 1000010
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;
}
void print(){
printf(" [1st]");fs.first.print();
printf(" [2nd]");fs.second.print();
}
};
//getmerge
template <typename T>
class segtree{
private:
int begin,end;
stack<int> st1,stL,stR,rollback;
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();
}
};
vector<NODE> t;
//
inline T merge(NODE &l,NODE &r){return l.get()+r.get();}
inline T merge(T &l,NODE &r){return l+r.get();}
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_TREE_SIZE){}
segtree(int bg,int ed):begin(bg),end(ed),t(SEG_TREE_SIZE){
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;
}
};
#define MAX_H
int main(){
int res=0;
segtree<ND> up(0,1000020);
segtree<ND> down(0,1000020);
int N;cin>>N;
for(int i = 0; i < N; i++){
int h;cin>>h;h++;
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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0