oj.uz

Submission #1082497

# Submission time Handle Problem Language Result Execution time Memory
1082497 2024-08-31T13:55:01 Z 4QT0R Wall (IOI14_wall) C++17
0 / 100
 28 ms 33220 KB 
#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
#define pii pair<int,int>

const int base=1<<21;
pii tree[2*base];
int ans[2000003];

void lazy_prop(int v){
	if (v>=base)return;
	tree[2*v].first=max(tree[2*v].first,tree[v].first);
	tree[2*v].second=min(tree[2*v].second,tree[v].second);
	tree[2*v+1].first=max(tree[2*v+1].first,tree[v].first);
	tree[2*v+1].second=min(tree[2*v+1].second,tree[v].second);
	tree[v]={min(tree[2*v].first,tree[2*v+1].first),max(tree[2*v].second,tree[2*v+1].second)};
}

void update(int v, int l, int p, int a, int b, pii op){
	if (a<=l && p<=b){
		if (op.first==0){
			tree[v].first=max(tree[v].first,op.second);
			tree[v].second=max(tree[v].second,tree[v].first);
		}
		else{
			tree[v].second=min(tree[v].second,op.second);
			tree[v].first=min(tree[v].second,tree[v].first);
		}
		lazy_prop(v);
		return;
	}
	else if (p<a || b<l){
		lazy_prop(v);
		return;
	}
	else{
		lazy_prop(v);
		update(2*v,l,(l+p)/2,a,b,op);
		update(2*v+1,(l+p)/2+1,p,a,b,op);
		tree[v]={min(tree[2*v].first,tree[2*v+1].first),max(tree[2*v].second,tree[2*v+1].second)};
	}
}

void finalProp(int v){
	if (v>=base)return;
	lazy_prop(v);
	finalProp(2*v);
	finalProp(2*v+1);
}

void buildWall(int n, int k, int op[], int left[], int right[],int height[], int finalHeight[]){
	for (int i = 0; i<k; i++)update(1,0,base-1,left[i],right[i],{op[i],height[i]});
	finalProp(1);
	for (int i = 0; i<n; i++)finalHeight[i]=tree[base+i].first;
}

Subtask #1
0 / 8.0

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

Subtask #2
0 / 24.0

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

Subtask #3
0 / 29.0

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

Subtask #4
0 / 39.0

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