oj.uz

Submission #1062920

# Submission time Handle Problem Language Result Execution time Memory
1062920 2024-08-17T11:55:02 Z YassirSalama Wall (IOI14_wall) C++17
61 / 100
 979 ms 262144 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
  if (node->left->max == node->right->max) {
		node->max = node->left->max;
		node->smax = max(node->left->smax, node->right->smax);
	} else {
		if (node->left->max > node->right->max) {
			node->max = node->left->max;
			node->smax = max(node->left->smax, node->right->max);
		} else {
			node->max = node->right->max;
			node->smax = max(node->left->max, node->right->smax);
		}
	}
 
	// min
	if (node->left->min == node->right->min) {
		node->min = node->left->min;
		node->smin = min(node->left->smin, node->right->smin);
	} else {
		if (node->left->min < node->right->min) {
			node->min = node->left->min;
			node->smin = min(node->left->smin, node->right->min);
		} else {
			node->min = node->right->min;
			node->smin = min(node->left->min, node->right->smin);
		}
	}
}
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 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 9 ms 1804 KB Output is correct
5 Correct 8 ms 1628 KB Output is correct
6 Correct 6 ms 1800 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 77 ms 8016 KB Output is correct
3 Correct 57 ms 5972 KB Output is correct
4 Correct 141 ms 21328 KB Output is correct
5 Correct 158 ms 21764 KB Output is correct
6 Correct 203 ms 21840 KB Output is correct

Subtask #3
29.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 8 ms 1808 KB Output is correct
5 Correct 6 ms 1628 KB Output is correct
6 Correct 6 ms 1628 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 78 ms 8180 KB Output is correct
9 Correct 57 ms 5968 KB Output is correct
10 Correct 146 ms 21328 KB Output is correct
11 Correct 154 ms 21844 KB Output is correct
12 Correct 201 ms 21840 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 84 ms 8240 KB Output is correct
15 Correct 45 ms 3152 KB Output is correct
16 Correct 808 ms 21480 KB Output is correct
17 Correct 359 ms 21608 KB Output is correct
18 Correct 368 ms 21560 KB Output is correct

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 Correct 2 ms 348 KB Output is correct
4 Correct 11 ms 1628 KB Output is correct
5 Correct 7 ms 1628 KB Output is correct
6 Correct 7 ms 1804 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 83 ms 8048 KB Output is correct
9 Correct 63 ms 6016 KB Output is correct
10 Correct 149 ms 21228 KB Output is correct
11 Correct 152 ms 21864 KB Output is correct
12 Correct 214 ms 21780 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 87 ms 8136 KB Output is correct
15 Correct 44 ms 3152 KB Output is correct
16 Correct 801 ms 21588 KB Output is correct
17 Correct 358 ms 21472 KB Output is correct
18 Correct 368 ms 21584 KB Output is correct
19 Runtime error 979 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -