oj.uz

Submission #770116

# Submission time Handle Problem Language Result Execution time Memory
770116 2023-06-30T19:02:45 Z YassirSalama Wall (IOI14_wall) C++14
0 / 100
 1 ms 212 KB 
#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e6;
int tree[4*MAXN];
int lazy[4*MAXN];
const int INF=2e9;
void push_max(int node,int l,int r){
	if(lazy[node]){
		tree[node]=max(tree[node],lazy[node]);
		if(l!=r) lazy[node<<1]=lazy[node],
				 lazy[node<<1|1]=lazy[node];
		lazy[node]=0;
	}
}
void update_max(int node,int l,int r,int ql,int qr,int x){
	push_max(node,l,r);
	if(ql<=l&&r<=qr) {
		lazy[node]=x;
		push_max(node,l,r);
		return;
	}
	int mid=(l+r)/2;
	if(ql<=mid) update_max(node<<1,l,mid,ql,qr,x);
	if(qr>mid) update_max(node<<1|1,mid+1,r,ql,qr,x);
	tree[node]=max(tree[node<<1],tree[node<<1|1]);
}
void build1(int node,int l,int r){
	push_max(node,l,r);
	if(l==r) {lazy[node]=INF;return;}
	int mid=(l+r)/2;
	build1(node<<1,l,mid);
	build1(node<<1|1,mid+1,r);
	tree[node]=max(tree[node<<1],tree[node<<1|1]);
	lazy[node]=INF;
}
void push_min(int node,int l,int r){
	if(lazy[node]!=INF){
		tree[node]=min(tree[node],lazy[node]);
		if(l!=r) lazy[node<<1]=lazy[node],
				 lazy[node<<1|1]=lazy[node];
		lazy[node]=INF;
	}
}
void update_min(int node,int l,int r,int ql,int qr,int x){
	push_min(node,l,r);
	if(ql<=l&&r<=qr) {
		lazy[node]=x;
		push_min(node,l,r);
		return;
	}
	int mid=(l+r)/2;
	if(ql<=mid) update_min(node<<1,l,mid,ql,qr,x);
	if(qr>mid) update_min(node<<1|1,mid+1,r,ql,qr,x);
	tree[node]=max(tree[node<<1],tree[node<<1|1]);
}
int query(int node,int l,int r,int ind){
	push_min(node,l,r);
	if(l==r) return tree[node];
	int mid=(l+r)/2;
	if(ind<=mid) return query(node<<1,l,mid,ind);
	return query(node<<1|1,mid+1,r,ind);
}
void buildWall(int n, int k, int op[], int left[], int right[], 
	int height[], int finalHeight[]){
	int nxtindex=0;
	for(int i=0;i<k;i++){
		if(op[i]==2) {
			nxtindex=i;
			break;
		}
	}
	for(int i=0;i<nxtindex;i++){
		int l=left[i];
		int r=right[i];
		int x=height[i];
		update_max(1,0,n-1,l,r,x);
	}
	build1(1,0,n-1);
	for(int i=nxtindex;i<k;i++){
		int l=left[i];
		int r=right[i];
		int x=height[i];
		update_min(1,0,n-1,l,r,x);
	}
	for(int i=0;i<n;i++){
		finalHeight[i]=query(1,0,n-1,i);
	}
	return;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -