結果
問題 |
No.1031 いたずら好きなお姉ちゃん
|
ユーザー |
|
提出日時 | 2020-04-22 14:23:15 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 347 ms / 3,500 ms |
コード長 | 1,900 bytes |
コンパイル時間 | 730 ms |
コンパイル使用メモリ | 73,560 KB |
実行使用メモリ | 240,640 KB |
最終ジャッジ日時 | 2024-10-11 07:13:56 |
合計ジャッジ時間 | 16,119 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 53 |
コンパイルメッセージ
main.cpp:32:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type] 32 | main() | ^~~~
ソースコード
#include<iostream> #include<vector> #include<algorithm> using namespace std; const int B=330; const int MAXN=100010; //const int MAXN=100; int N; int p[MAXN]; int MAX[MAXN/B],MIN[MAXN/B],CR[MAXN/B][MAXN],CL[MAXN/B][MAXN]; void calc(const vector<int>&A,int ans[MAXN]) { for(int i=0;i<MAXN;i++)ans[i]=-2e5; int cummin=N+1; int now=0; for(int i=A.size();i--;) { if(cummin>A[i]) { cummin=A[i]; ans[A[i]]=-now; now++; } } for(int i=1;i<MAXN;i++)ans[i]=max(ans[i],ans[i-1]); for(int i=0;i<MAXN;i++) { ans[i]+=now; if(ans[i]<0)ans[i]=0; } } main() { cin>>N; for(int i=0;i<N;i++)cin>>p[i]; for(int i=0;i+B<=N;i+=B) { vector<int>A(p+i,p+i+B); int id=i/B; calc(A,CR[id]); reverse(A.begin(),A.end()); calc(A,CL[id]); MAX[id]=MIN[id]=A[0]; for(int a:A) { if(MAX[id]<a)MAX[id]=a; if(MIN[id]>a)MIN[id]=a; } } long ans=0; for(int i=0;i<N;i++) { int now=0; int l=i,r=i+1; int P=p[i]; bool fl=true,fr=true; int LM=P,RM=P; while(l%B!=0) { l--; if(p[l]<LM) { now++; LM=p[l]; } else if(P<p[l]) { fl=false; break; } } if(fl) { while(l>=B) { int id=l/B-1; if(MAX[id]<P) { now+=CR[id][LM]; if(LM>MIN[id])LM=MIN[id]; l-=B; } else break; } while(l>0) { l--; if(p[l]<LM) { now++; LM=p[l]; } else if(P<p[l]) { break; } } } while(r<N&&r%B!=0) { r++; if(p[r-1]<RM) { now++; RM=p[r-1]; } else if(P<p[r-1]) { fr=false; break; } } if(fr) { while(r+B<=N) { int id=r/B; if(MAX[id]<P) { now+=CL[id][RM]; if(RM>MIN[id])RM=MIN[id]; r+=B; } else break; } while(r<N) { r++; if(p[r-1]<RM) { now++; RM=p[r-1]; } else if(P<p[r-1]) { break; } } } ans+=now; } cout<<ans<<endl; }