oj.uz

Submission #1062810

# Submission time Handle Problem Language Result Execution time Memory
1062810 2024-08-17T10:57:25 Z YassirSalama Wall (IOI14_wall) C++17
32 / 100
 3000 ms 28108 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
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
{
  ll min;
  ll max;
  ll smin;
  ll smax;
  ll cntmin;
  ll cntmax;
  ll 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=1e18;
    node->smax=-1e18;
    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
8.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 Correct 4 ms 348 KB Output is correct
4 Correct 190 ms 2392 KB Output is correct
5 Correct 333 ms 2416 KB Output is correct
6 Correct 388 ms 2400 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 128 ms 8016 KB Output is correct
3 Correct 61 ms 6992 KB Output is correct
4 Correct 182 ms 27472 KB Output is correct
5 Correct 145 ms 28108 KB Output is correct
6 Correct 180 ms 27988 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 3 ms 348 KB Output is correct
4 Correct 194 ms 2392 KB Output is correct
5 Correct 340 ms 2392 KB Output is correct
6 Correct 351 ms 2392 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 85 ms 8228 KB Output is correct
9 Correct 98 ms 6992 KB Output is correct
10 Correct 176 ms 27616 KB Output is correct
11 Correct 156 ms 27984 KB Output is correct
12 Correct 218 ms 28024 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 86 ms 8256 KB Output is correct
15 Correct 2013 ms 4136 KB Output is correct
16 Execution timed out 3032 ms 27000 KB Time limit exceeded
17 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 428 KB Output is correct
3 Correct 3 ms 348 KB Output is correct
4 Correct 182 ms 2404 KB Output is correct
5 Correct 357 ms 2400 KB Output is correct
6 Correct 344 ms 2396 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 85 ms 8020 KB Output is correct
9 Correct 62 ms 7128 KB Output is correct
10 Correct 176 ms 27516 KB Output is correct
11 Correct 143 ms 27984 KB Output is correct
12 Correct 184 ms 27928 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 130 ms 8268 KB Output is correct
15 Correct 2001 ms 4136 KB Output is correct
16 Execution timed out 3041 ms 26960 KB Time limit exceeded
17 Halted 0 ms 0 KB -