oj.uz

Submission #1062887

# Submission time Handle Problem Language Result Execution time Memory
1062887 2024-08-17T11:34:17 Z YassirSalama Wall (IOI14_wall) C++17
32 / 100
 3000 ms 31824 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->max);
  }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,int x){
  if(node->max<=x) return;
  node->max=x;
  if(l==r){
    node->min=node->max;
  }else{
    if(x<=node->min){
      node->min=x;
    }else if(x<node->smin){
      node->smin=x;
    }
  }
}
void pmax(Node* node,int l,int r,int x){
  if(node->min>=x)
    return;
  node->min=x;
  if(l==r){
    node->max=node->min;
  }else{
    if(x>=node->max){
      node->max=x;
    }else if(x>node->smax){
      node->smax=x;
    }
  }
}
void push(Node* node,int l,int r){
  if(l==r) return;
  pmin(node->left,l,(l+r)/2,node->max);
  pmin(node->right,(l+r)/2+1,r,node->max);
  pmax(node->left,l,(l+r)/2,node->min);
  pmax(node->right,(l+r)/2+1,r,node->min);
}
void p(Node* node,int l,int r){
  push(node,l,r);
  if(l==r) return;
  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){
    //put tag
    pmin(node,l,r,x);
    return;
  }
  p(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){
  p(node,l,r);
  if(l>qr||r<ql) return;
  if(node->min>=x) return;
  if(ql<=l&&r<=qr&&x<node->smin){
    //put tag
    pmax(node,l,r,x);
    return;
  }
  p(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
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 444 KB Output is correct
3 Correct 3 ms 344 KB Output is correct
4 Correct 92 ms 1884 KB Output is correct
5 Correct 165 ms 1884 KB Output is correct
6 Correct 178 ms 1880 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 84 ms 13912 KB Output is correct
3 Correct 57 ms 9808 KB Output is correct
4 Correct 164 ms 30804 KB Output is correct
5 Correct 155 ms 31784 KB Output is correct
6 Correct 201 ms 30372 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 Correct 3 ms 348 KB Output is correct
4 Correct 92 ms 1728 KB Output is correct
5 Correct 171 ms 1884 KB Output is correct
6 Correct 164 ms 1880 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 81 ms 14052 KB Output is correct
9 Correct 57 ms 9808 KB Output is correct
10 Correct 167 ms 30800 KB Output is correct
11 Correct 147 ms 31824 KB Output is correct
12 Correct 199 ms 30212 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 107 ms 13864 KB Output is correct
15 Correct 1060 ms 3632 KB Output is correct
16 Execution timed out 3014 ms 30348 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 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 91 ms 1876 KB Output is correct
5 Correct 173 ms 1872 KB Output is correct
6 Correct 166 ms 1880 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 81 ms 13820 KB Output is correct
9 Correct 56 ms 9808 KB Output is correct
10 Correct 165 ms 30940 KB Output is correct
11 Correct 150 ms 31824 KB Output is correct
12 Correct 209 ms 30404 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 84 ms 14016 KB Output is correct
15 Correct 957 ms 3684 KB Output is correct
16 Execution timed out 3100 ms 30288 KB Time limit exceeded
17 Halted 0 ms 0 KB -