oj.uz

Submission #1062826

# Submission time Handle Problem Language Result Execution time Memory
1062826 2024-08-17T11:04:38 Z YassirSalama Wall (IOI14_wall) C++17
32 / 100
 3000 ms 30288 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->min);
  }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){
  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 3 ms 348 KB Output is correct
4 Correct 166 ms 1880 KB Output is correct
5 Correct 307 ms 1896 KB Output is correct
6 Correct 306 ms 1880 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 99 ms 11556 KB Output is correct
3 Correct 60 ms 8276 KB Output is correct
4 Correct 190 ms 29128 KB Output is correct
5 Correct 184 ms 30288 KB Output is correct
6 Correct 174 ms 28748 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 344 KB Output is correct
3 Correct 3 ms 444 KB Output is correct
4 Correct 164 ms 1864 KB Output is correct
5 Correct 310 ms 1884 KB Output is correct
6 Correct 318 ms 1884 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 93 ms 13100 KB Output is correct
9 Correct 59 ms 8924 KB Output is correct
10 Correct 176 ms 28744 KB Output is correct
11 Correct 165 ms 29488 KB Output is correct
12 Correct 176 ms 28468 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 86 ms 12620 KB Output is correct
15 Correct 1931 ms 3624 KB Output is correct
16 Execution timed out 3046 ms 28220 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 172 ms 1880 KB Output is correct
5 Correct 315 ms 1880 KB Output is correct
6 Correct 304 ms 1880 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 114 ms 12640 KB Output is correct
9 Correct 59 ms 9044 KB Output is correct
10 Correct 175 ms 28748 KB Output is correct
11 Correct 139 ms 29524 KB Output is correct
12 Correct 179 ms 28500 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 87 ms 12784 KB Output is correct
15 Correct 1858 ms 3664 KB Output is correct
16 Execution timed out 3038 ms 28192 KB Time limit exceeded
17 Halted 0 ms 0 KB -