oj.uz

Submission #901924

# Submission time Handle Problem Language Result Execution time Memory
901924 2024-01-10T04:19:26 Z Muhammad_Aneeq Wall (IOI14_wall) C++17
100 / 100
 748 ms 200916 KB 
#include <iostream>
#include <algorithm>
#include "wall.h"
using namespace std;
struct seg
{
	int mi=0,ma=0,lazy=0;
	int ty=-1;	
};
int const MAXN=4194304;
seg* St[MAXN];
void push(int i)
{
	St[i*2]->lazy=St[i*2+1]->lazy=St[i]->lazy;
	St[i*2]->ty=St[i*2+1]->ty=St[i]->ty;
	St[i*2]->mi=St[i*2+1]->mi=St[i]->lazy;
	St[i*2]->ma=St[i*2+1]->ma=St[i]->lazy;
	St[i]->ty=-1;
}
void add(int i,int st,int en,int l,int r,int val)
{
	if (st>r||en<l)
		return;
	if (st>=l&&en<=r)
	{
		if (St[i]->mi>=val)
			return;
		if (St[i]->ma<=val)
		{
			St[i]->mi=St[i]->ma=val;
			St[i]->ty=-1;
			if (st!=en)
			{
				St[i*2]->lazy=St[i*2+1]->lazy=val;
				St[i*2]->ty=St[i*2+1]->ty=1;
				St[i*2]->mi=St[i*2+1]->mi=val;
				St[i*2]->ma=St[i*2+1]->ma=val;
			}
			return;
		}
	}
	if (St[i]->ty!=-1)
		push(i);
	int mid=(st+en)/2;
	add(i*2,st,mid,l,r,val);add(i*2+1,mid+1,en,l,r,val);
	St[i]->mi=min(St[i*2]->mi,St[i*2+1]->mi);
	St[i]->ma=max(St[i*2]->ma,St[i*2+1]->ma);
}
void sub(int i,int st,int en,int l,int r,int val)
{
	if (st>r||en<l)
		return;
	if (st>=l&&en<=r)
	{
		if (St[i]->ma<=val)
			return;
		if (St[i]->mi>=val)
		{
			St[i]->mi=St[i]->ma=val;
			St[i]->ty=-1;
			if (st!=en)
			{
				St[i*2]->lazy=St[i*2+1]->lazy=val;
				St[i*2]->ty=St[i*2+1]->ty=2;
				St[i*2]->mi=St[i*2+1]->mi=val;
				St[i*2]->ma=St[i*2+1]->ma=val;
			}
			return;
		}
	}
	if (St[i]->ty!=-1)
		push(i);
	int mid=(st+en)/2;
	sub(i*2,st,mid,l,r,val);sub(i*2+1,mid+1,en,l,r,val);
	St[i]->mi=min(St[i*2]->mi,St[i*2+1]->mi);
	St[i]->ma=max(St[i*2]->ma,St[i*2+1]->ma);
}
int get(int i,int r,int st,int en)
{
	if (st==en)
		return St[i]->mi;
	if (St[i]->ty!=-1)
		push(i);
	int mid=(st+en)/2;
	if (r<=mid)
		return get(i*2,r,st,mid);
	return get(i*2+1,r,mid+1,en);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
	for (int i=0;i<MAXN;i++)
	{
		St[i]=NULL;
		St[i]=new seg();
	}
	for (int i=0;i<k;i++)
	{
		if (op[i]==1)
			add(1,0,n-1,left[i],right[i],height[i]);
		else
			sub(1,0,n-1,left[i],right[i],height[i]);
	}
	for (int i=0;i<n;i++)
		finalHeight[i]=get(1,i,0,n-1);
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 164376 KB Output is correct
2 Correct 102 ms 164552 KB Output is correct
3 Correct 106 ms 164368 KB Output is correct
4 Correct 107 ms 164588 KB Output is correct
5 Correct 107 ms 164688 KB Output is correct
6 Correct 117 ms 164536 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 164712 KB Output is correct
2 Correct 206 ms 172368 KB Output is correct
3 Correct 227 ms 167900 KB Output is correct
4 Correct 437 ms 172972 KB Output is correct
5 Correct 303 ms 173396 KB Output is correct
6 Correct 298 ms 173448 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 164432 KB Output is correct
2 Correct 110 ms 164560 KB Output is correct
3 Correct 102 ms 164436 KB Output is correct
4 Correct 114 ms 164640 KB Output is correct
5 Correct 106 ms 164688 KB Output is correct
6 Correct 106 ms 164668 KB Output is correct
7 Correct 115 ms 164432 KB Output is correct
8 Correct 210 ms 172652 KB Output is correct
9 Correct 214 ms 167756 KB Output is correct
10 Correct 460 ms 173100 KB Output is correct
11 Correct 303 ms 173436 KB Output is correct
12 Correct 295 ms 173396 KB Output is correct
13 Correct 100 ms 164432 KB Output is correct
14 Correct 208 ms 172368 KB Output is correct
15 Correct 133 ms 165152 KB Output is correct
16 Correct 580 ms 173160 KB Output is correct
17 Correct 300 ms 173136 KB Output is correct
18 Correct 303 ms 173112 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 164520 KB Output is correct
2 Correct 107 ms 164504 KB Output is correct
3 Correct 105 ms 164436 KB Output is correct
4 Correct 107 ms 164500 KB Output is correct
5 Correct 109 ms 164688 KB Output is correct
6 Correct 110 ms 164692 KB Output is correct
7 Correct 102 ms 164564 KB Output is correct
8 Correct 205 ms 172360 KB Output is correct
9 Correct 215 ms 167764 KB Output is correct
10 Correct 460 ms 172908 KB Output is correct
11 Correct 304 ms 173520 KB Output is correct
12 Correct 301 ms 173648 KB Output is correct
13 Correct 101 ms 164436 KB Output is correct
14 Correct 209 ms 172376 KB Output is correct
15 Correct 127 ms 164992 KB Output is correct
16 Correct 604 ms 173188 KB Output is correct
17 Correct 306 ms 173268 KB Output is correct
18 Correct 302 ms 173192 KB Output is correct
19 Correct 706 ms 190348 KB Output is correct
20 Correct 743 ms 198272 KB Output is correct
21 Correct 702 ms 200916 KB Output is correct
22 Correct 706 ms 198488 KB Output is correct
23 Correct 708 ms 198472 KB Output is correct
24 Correct 708 ms 198308 KB Output is correct
25 Correct 703 ms 198228 KB Output is correct
26 Correct 708 ms 200784 KB Output is correct
27 Correct 711 ms 200916 KB Output is correct
28 Correct 748 ms 198464 KB Output is correct
29 Correct 722 ms 198460 KB Output is correct
30 Correct 731 ms 198584 KB Output is correct