oj.uz

Submission #1062822

# Submission time Handle Problem Language Result Execution time Memory
1062822 2024-08-17T11:02:34 Z YassirSalama Wall (IOI14_wall) C++17
0 / 100
 109 ms 11744 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e6 + 100;
template<typename T>
void dbg(const T& t){
  cout<<t<<endl;
  return;
}
template<typename T,typename... Args>
void dbg(const T& t,const Args&... args){
  cout<<t<<" , ";
  dbg(args...);
}
#define dbg(...) cout<<"("<<#__VA_ARGS__<<") : "<<endl;dbg(__VA_ARGS__);

struct Node
{
  int min;
  int max;
  int smin;
  int smax;
  int lzmin=-1,lzmax=-1;
  bool lazy=false;
  Node* left,*right;
  Node() : left(nullptr),right(nullptr){}
};
void pull(Node* node){
  //for min
  node->min=min(node->left->min,node->right->min);
  if(node->left->min==node->right->min){
    node->smin=min(node->left->smin,node->right->smin);
  }else if(node->left->min==node->min){
    node->smin=min(node->left->smin,node->right->min);
  }else node->smin=min(node->right->smin,node->left->min);
  
  //for max
  node->max=max(node->left->max,node->right->max);
  if(node->left->max==node->right->max){
    node->smax=max(node->left->smax,node->right->smax);
  }else if(node->left->max==node->max){
    node->smax=max(node->left->smax,node->right->max);
  }else node->smax=max(node->right->smax,node->left->max);
}
void build(Node* node,int l,int r){
  if(l==r){
    node->min=node->max=0;
    node->smin=1e9;
    node->smax=-1e9;
    return;
  }
  int mid=(l+r)/2;
  node->left=new Node();
  node->right=new Node();
  build(node->left,l,mid);
  build(node->right,mid+1,r);
  pull(node);
}
void pmin(Node* node,int l,int r){
  if(node->smax<=node->lzmin&&node->lzmin<node->max){
    node->max=node->lzmin;
    node->min=min(node->min,node->lzmin);
    if(l==r) return;
    node->left->lazy=1;
    node->right->lazy=1;
    node->left->lzmin=node->lzmin;
    node->right->lzmin=node->lzmin;
  }
  return;
}
void pmax(Node* node,int l,int r){
  if(node->smin>=node->lzmax&&node->lzmax>node->min){
    node->min=node->lzmax;
    node->max=max(node->max,node->lzmax);
    if(l==r) return;
    node->left->lazy=1;
    node->right->lazy=1;
    node->left->lzmax=node->lzmax;
    node->right->lzmax=node->lzmax;
  }
  return;
}
void push(Node* node,int l,int r){
  if(node->lazy==false) return;
  if(node->lzmin!=-1){
    pmin(node,l,r);
  }
  if(node->lzmax!=-1){
    pmax(node,l,r);
  }
  node->lazy=false;
  node->lzmin=node->lzmax=-1;
}
void p(Node* node,int l,int r){
  push(node,l,r);
  if(l==r) return;
  push(node->left,l,(l+r)/2);
  push(node->right,(l+r)/2+1,r);
  pull(node);
}
void setmin(Node* node,int l,int r,int ql,int qr,int x){
  p(node,l,r);
  if(l>qr||r<ql) return;
  if(node->max<=x) return;
  if(ql<=l&&r<=qr&&node->smax<=x&&x<node->max){
    //put tag
    node->lazy=1;
    node->lzmin=x;
    p(node,l,r);
    return;
  }
  int mid=(l+r)/2;
  setmin(node->left,l,mid,ql,qr,x);
  setmin(node->right,mid+1,r,ql,qr,x);
  p(node,l,r);
}
void setmax(Node* node,int l,int r,int ql,int qr,int x){
  p(node,l,r);
  if(l>qr||r<ql) return;
  if(node->min>=x) return;
  if(ql<=l&&r<=qr&&node->smin>=x&&x>node->min){
    //put tag
    node->lazy=1;
    node->lzmax=x;
    p(node,l,r);
    return;
  }
  int mid=(l+r)/2;
  setmax(node->left,l,mid,ql,qr,x);
  setmax(node->right,mid+1,r,ql,qr,x);
  p(node,l,r);  
}
int query(Node* node,int l,int r,int ql){
  push(node,l,r);
  if(l==r) return node->min;
  int mid = (l+r)/2;
  if(ql<=mid) return query(node->left,l,mid,ql);
  else return query(node->right,mid+1,r,ql);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int ans[])
{
  Node* root=new Node();
  build(root,0,n-1);
  for(int i=0;i<k;i++){
    int t=op[i];
    int l=left[i];
    int r=right[i];
    int x=height[i];
    if(t==1){
      setmax(root,0,n-1,l,r,x);
    }else{
      setmin(root,0,n-1,l,r,x);
    }
  }
  for(int i=0;i<n;i++){
    ans[i]=query(root,0,n-1,i);
  }
  return;
}

Subtask #1
0 / 8.0

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

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 109 ms 11744 KB Output is correct
3 Incorrect 72 ms 8340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

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

Subtask #4
0 / 39.0

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