oj.uz

Submission #1062910

# Submission time Handle Problem Language Result Execution time Memory
1062910 2024-08-17T11:49:57 Z YassirSalama Wall (IOI14_wall) C++17
100 / 100
 1554 ms 102480 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e6 + 100;
struct Node{
  int min;
  int max;
  int smin;
  int smax;
} tree[4*maxn];
void pull(int node){
  //for min
  if (tree[node << 1].max == tree[node << 1 | 1].max) {
		tree[node].max = tree[node << 1].max;
		tree[node].smax = max(tree[node << 1].smax, tree[node << 1 | 1].smax);
	} else {
		if (tree[node << 1].max > tree[node << 1 | 1].max) {
			tree[node].max = tree[node << 1].max;
			tree[node].smax = max(tree[node << 1].smax, tree[node << 1 | 1].max);
		} else {
			tree[node].max = tree[node << 1 | 1].max;
			tree[node].smax = max(tree[node << 1].max, tree[node << 1 | 1].smax);
		}
	}
 
	// min
	if (tree[node << 1].min == tree[node << 1 | 1].min) {
		tree[node].min = tree[node << 1].min;
		tree[node].smin = min(tree[node << 1].smin, tree[node << 1 | 1].smin);
	} else {
		if (tree[node << 1].min < tree[node << 1 | 1].min) {
			tree[node].min = tree[node << 1].min;
			tree[node].smin = min(tree[node << 1].smin, tree[node << 1 | 1].min);
		} else {
			tree[node].min = tree[node << 1 | 1].min;
			tree[node].smin = min(tree[node << 1].min, tree[node << 1 | 1].smin);
		}
	}
}
void build(int node,int l,int r){
  if(l==r){
    tree[node].min=tree[node].max=0;
    tree[node].smin=1e9;
    tree[node].smax=-1e9;
    return;
  }
  int mid=(l+r)/2;
  build(node*2,l,mid);
  build(node*2+1,mid+1,r);
  pull(node);
}
void pmin(int node,int l,int r,int x){
  if(tree[node].max<=x) return;
  tree[node].max=x;
  if(l==r){
    tree[node].min=tree[node].max;
  }else{
    if(x<=tree[node].min){
      tree[node].min=x;
    }else if(x<tree[node].smin){
      tree[node].smin=x;
    }
  }
}
void pmax(int node,int l,int r,int x){
  if(tree[node].min>=x)
    return;
  tree[node].min=x;
  if(l==r){
    tree[node].max=tree[node].min;
  }else{
    if(x>=tree[node].max){
      tree[node].max=x;
    }else if(x>tree[node].smax){
      tree[node].smax=x;
    }
  }
}
void push(int node,int l,int r){
  if(l==r) return;
  pmin(node*2,l,(l+r)/2,tree[node].max);
  pmin(node*2+1,(l+r)/2+1,r,tree[node].max);
  pmax(node*2,l,(l+r)/2,tree[node].min);
  pmax(node*2+1,(l+r)/2+1,r,tree[node].min);
}
void setmin(int node,int l,int r,int ql,int qr,int x){
  push(node,l,r);
  if(l>qr||r<ql||tree[node].max<=x) return;
  if(ql<=l&&r<=qr&&tree[node].smax<x){
    //put tag
    pmin(node,l,r,x);
    return;
  }
  push(node,l,r);
  int mid=(l+r)/2;
  setmin(node*2,l,mid,ql,qr,x);
  setmin(node*2+1,mid+1,r,ql,qr,x);
  pull(node);
}
void setmax(int node,int l,int r,int ql,int qr,int x){
  push(node,l,r);
  if(l>qr||r<ql||tree[node].min>=x) return;
  if(ql<=l&&r<=qr&&x<tree[node].smin){
    //put tag
    pmax(node,l,r,x);
    return;
  }
  push(node,l,r);
  int mid=(l+r)/2;
  setmax(node*2,l,mid,ql,qr,x);
  setmax(node*2+1,mid+1,r,ql,qr,x);
  pull(node);
}
int query(int node,int l,int r,int ql){
  push(node,l,r);
  if(l==r) return tree[node].min;
  int mid = (l+r)/2;
  if(ql<=mid) return query(node*2,l,mid,ql);
  else return query(node*2+1,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(1,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(1,0,n-1,l,r,x);
    }else{
      setmin(1,0,n-1,l,r,x);
    }
  }
  for(int i=0;i<n;i++){
    ans[i]=query(1,0,n-1,i);
  }
  return;
}

Compilation message

wall.cpp: In function 'void buildWall(int, int, int*, int*, int*, int*, int*)':
wall.cpp:123:9: warning: unused variable 'root' [-Wunused-variable]
  123 |   Node* root=new Node();
      |         ^~~~

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 3 ms 348 KB Output is correct
4 Correct 9 ms 1076 KB Output is correct
5 Correct 8 ms 1116 KB Output is correct
6 Correct 7 ms 1076 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 79 ms 8136 KB Output is correct
3 Correct 56 ms 4684 KB Output is correct
4 Correct 160 ms 12768 KB Output is correct
5 Correct 179 ms 13392 KB Output is correct
6 Correct 240 ms 13328 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 9 ms 1116 KB Output is correct
5 Correct 7 ms 1076 KB Output is correct
6 Correct 7 ms 1076 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 89 ms 8188 KB Output is correct
9 Correct 55 ms 4692 KB Output is correct
10 Correct 155 ms 12944 KB Output is correct
11 Correct 160 ms 13392 KB Output is correct
12 Correct 232 ms 13392 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 88 ms 8140 KB Output is correct
15 Correct 43 ms 1880 KB Output is correct
16 Correct 808 ms 13152 KB Output is correct
17 Correct 444 ms 13148 KB Output is correct
18 Correct 444 ms 22100 KB Output is correct

Subtask #4
39.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 2 ms 348 KB Output is correct
4 Correct 9 ms 1116 KB Output is correct
5 Correct 7 ms 1076 KB Output is correct
6 Correct 7 ms 1124 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 78 ms 8072 KB Output is correct
9 Correct 56 ms 4688 KB Output is correct
10 Correct 147 ms 12884 KB Output is correct
11 Correct 177 ms 13268 KB Output is correct
12 Correct 236 ms 13392 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 87 ms 8020 KB Output is correct
15 Correct 43 ms 1880 KB Output is correct
16 Correct 831 ms 13148 KB Output is correct
17 Correct 435 ms 13144 KB Output is correct
18 Correct 434 ms 22060 KB Output is correct
19 Correct 1375 ms 102292 KB Output is correct
20 Correct 1358 ms 99920 KB Output is correct
21 Correct 1403 ms 102288 KB Output is correct
22 Correct 1443 ms 99920 KB Output is correct
23 Correct 1440 ms 99864 KB Output is correct
24 Correct 1380 ms 99988 KB Output is correct
25 Correct 1408 ms 99920 KB Output is correct
26 Correct 1456 ms 102480 KB Output is correct
27 Correct 1486 ms 102480 KB Output is correct
28 Correct 1419 ms 99844 KB Output is correct
29 Correct 1554 ms 99936 KB Output is correct
30 Correct 1437 ms 99924 KB Output is correct