oj.uz

Submission #1062922

# Submission time Handle Problem Language Result Execution time Memory
1062922 2024-08-17T11:55:29 Z YassirSalama Wall (IOI14_wall) C++17
100 / 100
 1180 ms 214236 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;
  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 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 8 ms 1372 KB Output is correct
5 Correct 6 ms 1492 KB Output is correct
6 Correct 7 ms 1372 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 83 ms 8020 KB Output is correct
3 Correct 53 ms 5336 KB Output is correct
4 Correct 135 ms 18188 KB Output is correct
5 Correct 142 ms 18512 KB Output is correct
6 Correct 199 ms 18516 KB Output is correct

Subtask #3
29.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 2 ms 348 KB Output is correct
4 Correct 8 ms 1488 KB Output is correct
5 Correct 6 ms 1368 KB Output is correct
6 Correct 6 ms 1368 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 77 ms 8192 KB Output is correct
9 Correct 51 ms 5452 KB Output is correct
10 Correct 137 ms 18032 KB Output is correct
11 Correct 145 ms 18608 KB Output is correct
12 Correct 202 ms 18636 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 82 ms 8188 KB Output is correct
15 Correct 41 ms 2640 KB Output is correct
16 Correct 771 ms 18260 KB Output is correct
17 Correct 361 ms 18260 KB Output is correct
18 Correct 369 ms 18256 KB Output is correct

Subtask #4
39.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 8 ms 1488 KB Output is correct
5 Correct 7 ms 1488 KB Output is correct
6 Correct 6 ms 1368 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 78 ms 8024 KB Output is correct
9 Correct 51 ms 5456 KB Output is correct
10 Correct 135 ms 18008 KB Output is correct
11 Correct 144 ms 18532 KB Output is correct
12 Correct 214 ms 18632 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 87 ms 8060 KB Output is correct
15 Correct 45 ms 2532 KB Output is correct
16 Correct 747 ms 18260 KB Output is correct
17 Correct 362 ms 18480 KB Output is correct
18 Correct 357 ms 18256 KB Output is correct
19 Correct 1113 ms 214032 KB Output is correct
20 Correct 1131 ms 211792 KB Output is correct
21 Correct 1127 ms 214236 KB Output is correct
22 Correct 1180 ms 211540 KB Output is correct
23 Correct 1105 ms 211540 KB Output is correct
24 Correct 1159 ms 211752 KB Output is correct
25 Correct 1101 ms 211496 KB Output is correct
26 Correct 1151 ms 214056 KB Output is correct
27 Correct 1122 ms 214096 KB Output is correct
28 Correct 1137 ms 211496 KB Output is correct
29 Correct 1103 ms 211724 KB Output is correct
30 Correct 1115 ms 211752 KB Output is correct