Submission #1282963

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282963		Faisal_Saqib	벽 (IOI14_wall)	C++20	100 / 100	800 ms	214344 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
// const int N=2e6+10;
// int val[N];
const int inf=1e9;
struct SegmentTree
{
    int mx=-inf,mi=inf;
    // v will change to min(mi,max(v,mx))
    SegmentTree *next[2];
    int l,r;
    SegmentTree(int s,int e)
    {
        l=s,r=e;
        if(l==r)
        {
            return;
        }
        int mid=(l+r)/2;
        next[0]=new SegmentTree(s,mid);
        next[1]=new SegmentTree(mid+1,e);
    }
    void propagate()
    {
        next[0]->mx=min(mi,max(mx,next[0]->mx));
        next[0]->mi=min(mi,max(mx,next[0]->mi));
        next[1]->mx=min(mi,max(mx,next[1]->mx));
        next[1]->mi=min(mi,max(mx,next[1]->mi));
        mx=-inf;
        mi=inf;
    }
    void Update(int ql,int qr,int v,bool ty) // ty=0 for max operation
    {
        // cout<<ql<<' '<<qr<<' '<<l<<' '<<r<<endl;

      if(r<ql or qr<l)return;
        if(ql<=l and r<=qr)
        {
            // min(mi,max(mx,prev))
            // mx<=mi
            // prev < mx     mx
            // mx<=prev<=mi  prev
            // mi < prev     mi
            if(!ty)
            {
                mx=max(mx,v);
                mi=max(mi,v);
            }
            else{
                mx=min(mx,v);
                mi=min(mi,v);
            }
            return;
        }

        // send the current nodes update down
        propagate();
        next[0]->Update(ql,qr,v,ty);
        next[1]->Update(ql,qr,v,ty);
    }
    int get(int i,int o)
    {
        if(l==r)
        {
            return min(mi,max(mx,o));
        }
        propagate();
        return next[(i>((l+r)/2))]->get(i,o);
    }
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  // for(int i=0;i<n;i++)
  // {
  //   val[i]=
  // }
    // cout<<"Here6"<<endl;

  SegmentTree* sg=new SegmentTree(0,n-1);
    // cout<<"Here3"<<endl;

  for(int i=0;i<k;i++)
  {
    // cout<<"Here2"<<endl;
    // left[i]--;
    // right[i]--;
    sg->Update(left[i],right[i],height[i],op[i]-1);
  }
  for(int i=0;i<n;i++)
  {
    // cout<<""
    finalHeight[i]=sg->get(i,0);
  }
  return;
}

• Subtask 1: 8 / 8
• Subtask 2: 24 / 24
• Subtask 3: 29 / 29
• Subtask 4: 39 / 39