oj.uz

Submission #1104268

# Submission time Handle Problem Language Result Execution time Memory
1104268 2024-10-23T11:14:17 Z vjudge1 Wall (IOI14_wall) C++14
0 / 100
 159 ms 40876 KB 
#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
struct node{
  int mi;
  node() : mi(0) {}
}sg[8000005];
int lazy1[8000005],lazy2[8000005];
void push(int u,int l,int r)
{
  if(lazy1[u]!=-1)
  {
    sg[u].mi = max(sg[u].mi,lazy1[u]);
    if(l!=r)
    {
      lazy1[2*u] = max(lazy1[2*u],lazy1[u]);
      lazy2[2*u] = max(lazy2[2*u],lazy1[u]);
  
      lazy1[2*u+1] = max(lazy1[2*u+1],lazy1[u]);
      lazy2[2*u+1] = max(lazy2[2*u+1],lazy1[u]); 
        
    }
    lazy1[u] = -1;  
  }
  if(lazy2[u]!=-1)
  {
    sg[u].mi = min(sg[u].mi,lazy2[u]);
    if(l!=r)
    {
      lazy1[2*u] = min(lazy1[2*u],lazy2[u]);
      lazy2[2*u] = min(lazy2[2*u],lazy2[u]);

      lazy1[2*u+1] = min(lazy1[2*u+1],lazy2[u]);
      lazy2[2*u+1] = min(lazy2[2*u+1],lazy2[u]);
    }
    lazy2[u] = -1; 
  }
}


void update_max(int u,int l,int r,int sl,int sr ,int x)
{
  push(u,l,r);
  if(l>r or l>sr or r<sl) return;
  if(sl<=l and r<=sr) 
  {

    lazy1[u] = x;
    push(u,l,r);
    return;
  }
  int m=(l+r)/2;
  update_max(2*u,l,m,sl,sr,x);
  update_max(2*u+1,m+1,r,sl,sr,x);
}
void update_min(int u,int l,int r,int sl,int sr ,int x)
{
  push(u,l,r);
  if(l>r or l>sr or r<sl) return;
  if(sl<=l and r<=sr)
  {
    lazy2[u] = x;
    push(u,l,r);
    return;
  }
  int m=(l+r)/2;
  update_min(2*u,l,m,sl,sr,x);
  update_min(2*u+1,m+1,r,sl,sr,x);
}
int ans[8000005];
void query(int u,int l,int r)
{
  push(u,l,r);
  if(r<l) return;
  if(l==r)
  {
    ans[l-1] = sg[u].mi;
    return ;
  }
  int m=(l+r)/2;
  query(2*u,l,m);
  query(2*u+1,m+1,r);
  
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  for(int i=0;i<k;i++)
  {
    if(op[i]==1)
    {
      update_max(1,1,n,left[i]+1,right[i]+1,height[i]);
    }
    else
    {
      update_min(1,1,n,left[i]+1,right[i]+1,height[i]);
    }
    
  }
  query(1,1,n);
  
  for(int i=0;i<n;i++) finalHeight[i]=ans[i];
  return;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 33104 KB Output is correct
2 Correct 7 ms 33104 KB Output is correct
3 Incorrect 7 ms 33104 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 33104 KB Output is correct
2 Correct 93 ms 40876 KB Output is correct
3 Incorrect 159 ms 36944 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 33104 KB Output is correct
2 Correct 7 ms 33104 KB Output is correct
3 Incorrect 6 ms 33104 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 33104 KB Output is correct
2 Correct 6 ms 33104 KB Output is correct
3 Incorrect 7 ms 33216 KB Output isn't correct
4 Halted 0 ms 0 KB -