oj.uz

Submission #239003

# Submission time Handle Problem Language Result Execution time Memory
239003 2020-06-14T03:20:10 Z T0p_ Wall (IOI14_wall) C++14
0 / 100
 5 ms 384 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;

#define N 2000002

int mx[N<<2], mn[N<<2];
pair<int, int> laz[N<<2];

void push_lazy(int idx, int l, int r)
{
	if(laz[idx].first)
	{
		mx[idx] = mn[idx] = laz[idx].second;
		if(l != r) laz[idx<<1] = laz[idx<<1|1] = laz[idx];
		laz[idx] = {0, 0};
	}
}

void upd_mx(int idx, int l, int r, int a, int b, int h)
{
	push_lazy(idx, l, r);
	if(r < a || b < l || mn[idx] >= h) return ;
	if(a <= l && r <= b && mx[idx] <= h)
	{
		laz[idx] = {1, h};
		push_lazy(idx, l, r);
		return ;
	}
	int mid = (l+r)>>1;
	upd_mx(idx<<1, l, mid, a, b, h), upd_mx(idx<<1|1, mid+1, r, a, b, h);
	mx[idx] = max(mx[idx<<1], mx[idx<<1|1]);
}

void upd_mn(int idx, int l, int r, int a, int b, int h)
{
	push_lazy(idx, l, r);
	if(r < a || b < l || mx[idx] <= h) return ;
	if(a <= l && r <= b && mn[idx] >= h)
	{
		laz[idx] = {2, h};
		push_lazy(idx, l, r);
		return ;
	}
	int mid = (l+r)>>1;
	upd_mn(idx<<1, l, mid, a, b, h), upd_mn(idx<<1|1, mid+1, r, a, b, h);
	mn[idx] = min(mn[idx<<1], mn[idx<<1|1]);
}

void print(int idx, int l, int r)
{
	push_lazy(idx, l, r);
	if(l == r) return void(printf("%d\n",mx[idx]));
	int mid = (l+r)>>1;
	print(idx<<1, l, mid), print(idx<<1|1, mid+1, r);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
	for(int i=0 ; i<k ; i++)
	{
		switch(op[i])
		{
			case 1: upd_mx(1, 0, n-1, left[i], right[i], height[i]); break;
			case 2: upd_mn(1, 0, n-1, left[i], right[i], height[i]); break;
		}
	}
	print(1, 0, n-1);
  	return;
}

Subtask #1
0 / 8.0

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

Subtask #2
0 / 24.0

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

Subtask #3
0 / 29.0

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

Subtask #4
0 / 39.0

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