oj.uz

Submission #901913

# Submission time Handle Problem Language Result Execution time Memory
901913 2024-01-10T04:05:14 Z Muhammad_Aneeq Wall (IOI14_wall) C++17
61 / 100
 482 ms 33248 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=1e5;
seg St[4*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)
	{
		// cout<<r<<' '<<st<<'\n';
		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<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 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 5 ms 1116 KB Output is correct
5 Correct 4 ms 1116 KB Output is correct
6 Correct 4 ms 1116 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 110 ms 8104 KB Output is correct
3 Correct 106 ms 4688 KB Output is correct
4 Correct 305 ms 22356 KB Output is correct
5 Correct 204 ms 23632 KB Output is correct
6 Correct 199 ms 21836 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 1 ms 348 KB Output is correct
4 Correct 5 ms 1112 KB Output is correct
5 Correct 4 ms 1116 KB Output is correct
6 Correct 6 ms 1116 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 119 ms 13920 KB Output is correct
9 Correct 120 ms 8552 KB Output is correct
10 Correct 361 ms 22496 KB Output is correct
11 Correct 205 ms 23380 KB Output is correct
12 Correct 199 ms 21992 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 116 ms 13964 KB Output is correct
15 Correct 33 ms 2528 KB Output is correct
16 Correct 482 ms 22864 KB Output is correct
17 Correct 208 ms 22208 KB Output is correct
18 Correct 209 ms 22176 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 3 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 6 ms 1116 KB Output is correct
5 Correct 4 ms 1116 KB Output is correct
6 Correct 4 ms 1112 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 111 ms 13904 KB Output is correct
9 Correct 120 ms 8480 KB Output is correct
10 Correct 330 ms 22496 KB Output is correct
11 Correct 203 ms 23628 KB Output is correct
12 Correct 225 ms 22048 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 114 ms 13908 KB Output is correct
15 Correct 24 ms 2640 KB Output is correct
16 Correct 417 ms 22612 KB Output is correct
17 Correct 210 ms 22204 KB Output is correct
18 Correct 201 ms 22124 KB Output is correct
19 Runtime error 135 ms 33248 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -