ARC080-E YoungMaids (800)

頭の整理＋セグ木

方針は分かりやすいが、整理が難しい

構造体を初めて使った

セグ木は2Nまで初期化しよう

  1. #include<iostream>
  2. #include<algorithm>
  3. #include<vector>
  4. #include<queue>
  5. #define lol(i,n) for(int i=0;i<n;i++)
  6. #define mod 1000000007
  7. typedef long long ll;
  8. using namespace std;
  9.  
  10. #define N (1<<18)
  11. int seg[2][1<<19];
  12. void Init(){
  13. lol(i,N*2)lol(j,2)seg[j][i]=mod;
  14. }
  15. void Update(int i,int x,int flip){
  16. i+=N-1;
  17. seg[flip][i]=x;
  18. while(i){
  19. i=(i-1)/2;
  20. seg[flip][i]=min(seg[flip][i],x);
  21. }
  22. }
  23. int qry(int left,int right,int k,int a,int b,int flip){
  24. if(left<=a&&b<=right)return seg[flip][k];
  25. if(right<=a||b<=left)return mod;
  26. int m=(a+b)/2;
  27. return min(qry(left,right,k*2+1,a,m,flip),qry(left,right,k*2+2,m,b,flip));
  28. }
  29. int rmq(int left,int right,int flip){
  30. return qry(left,right+1,0,0,N,flip);
  31. }
  32.  
  33. int n;
  34. int p[200010];
  35. int at[200010];
  36.  
  37. struct P{
  38. int valL,valR;
  39. int placeL,placeR;
  40. int left,right,flip;
  41. bool operator< (const P &P1)const{
  42. return valL<P1.valL;
  43. };
  44. bool operator> (const P &P1)const{
  45. return valL>P1.valL;
  46. };
  47. };
  48. priority_queue<P,vector<P>,greater<P> >Q;
  49. void Qpush(int left,int right,int flip){
  50. if(left>right)return;
  51. int valL=rmq(left,right,flip);
  52. int placeL=at[valL];
  53. int valR=rmq(placeL,right,1-flip);
  54. int placeR=at[valR];
  55. P tmp;
  56. tmp.valL=valL,tmp.valR=valR;
  57. tmp.placeL=placeL,tmp.placeR=placeR;
  58. tmp.left=left,tmp.right=right,tmp.flip=flip;
  59. Q.push(tmp);
  60. }
  61.  
  62. int main(){
  63. Init();
  64. cin>>n;
  65. lol(i,n){
  66. cin>>p[i];
  67. at[p[i]]=i;
  68. Update(i,p[i],i%2);
  69. }
  70. Qpush(0,n-1,0);
  71. bool first=true;
  72. while(!Q.empty()){
  73. P now=Q.top();Q.pop();
  74. if(!first)cout<<" ";first=false;
  75. cout<<now.valL<<" "<<now.valR;
  76. Qpush(now.left,now.placeL-1,now.flip);
  77. Qpush(now.placeL+1,now.placeR-1,1-now.flip);
  78. Qpush(now.placeR+1,now.right,now.flip);
  79. }
  80. cout<<endl;
  81. return 0;
  82. }

700点チャレンジ3問目（800点やが）