oj.uz

Submission #1062800

# Submission time Handle Problem Language Result Execution time Memory
1062800 2024-08-17T10:54:38 Z YassirSalama Wall (IOI14_wall) C++17
24 / 100
 150 ms 22032 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 cntmin;
  int cntmax;
  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->min==node->left->min){
    if(node->min==node->right->min){
      node->cntmin=node->left->cntmin+node->right->cntmin;
      node->smin=min(node->left->smin,node->right->min);
    }else {
      node->smin=min({node->left->smin,node->right->min});
      node->cntmin=node->left->cntmin;
    }
  }else{
    node->smin=min({node->right->smin,node->left->min});
    node->cntmin=node->right->cntmin;
  }

  //for max
  node->max=max(node->left->max,node->right->max);
  if(node->max==node->left->max){
    if(node->max==node->right->max){
      node->cntmax=node->left->cntmax+node->right->cntmax;
      node->smax=max(node->left->smax,node->right->max);
    }else {
      node->smax=max({node->left->smax,node->right->max});
      node->cntmax=node->left->cntmax;
    }
  }else{
    node->smax=max({node->right->smax,node->left->max});
    node->cntmax=node->right->cntmax;
  }




}
void build(Node* node,int l,int r){
  if(l==r){
    node->min=node->max=0;
    node->cntmin=node->cntmax=1;
    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 push(Node* node,int l,int r){
  if(node->lazy==false) return;
  if(node->lzmin!=-1){
    if(node->smax<=node->lzmin&&node->lzmin<node->max){
      node->max=node->lzmin;
      node->min=min(node->min,node->lzmin);
      if(l!=r){
        node->left->lazy=1;
        node->right->lazy=1;
        node->left->lzmin=node->lzmin;
        node->right->lzmin=node->lzmin;
      }
    }
  }
  if(node->lzmax!=-1){
    if(node->smin>=node->lzmax&&node->lzmax>node->min){
      node->min=node->lzmax;
      node->max=max(node->max,node->lzmax);
      if(l!=r) {
        node->left->lazy=1;
        node->right->lazy=1;
        node->left->lzmax=node->lzmax;
        node->right->lzmax=node->lzmax;
      }
    }
  }
  node->lazy=false;
  node->lzmin=node->lzmax=-1;
}
void setmin(Node* node,int l,int r,int ql,int qr,int x){
  push(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;
    push(node,l,r);
    return;
  }
  push(node,l,r);
  int mid=(l+r)/2;
  setmin(node->left,l,mid,ql,qr,x);
  setmin(node->right,mid+1,r,ql,qr,x);
  pull(node);
}
void setmax(Node* node,int l,int r,int ql,int qr,int x){
  push(node,l,r);
  if(l>qr||r<ql||node->min>=x) return;
  if(ql<=l&&r<=qr&&node->smin>=x&&x>node->min){
    //put tag
    node->lazy=1;
    node->lzmax=x;
    push(node,l,r);
    return;
  }
  push(node,l,r);
  int mid=(l+r)/2;
  setmax(node->left,l,mid,ql,qr,x);
  setmax(node->right,mid+1,r,ql,qr,x);
  pull(node);
}
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 1 ms 348 KB Output is correct
3 Incorrect 2 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 78 ms 8132 KB Output is correct
3 Correct 52 ms 5968 KB Output is correct
4 Correct 150 ms 21296 KB Output is correct
5 Correct 123 ms 21844 KB Output is correct
6 Correct 142 ms 22032 KB Output is correct

Subtask #3
0 / 29.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 2 ms 344 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 600 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Incorrect 2 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -