oj.uz

Submission #901923

# Submission time Handle Problem Language Result Execution time Memory
901923 2024-01-10T04:16:53 Z Muhammad_Aneeq Wall (IOI14_wall) C++17
61 / 100
 513 ms 262144 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=2e6;
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)
		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<4*n;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 0 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 7 ms 4040 KB Output is correct
5 Correct 5 ms 3932 KB Output is correct
6 Correct 5 ms 3932 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 98 ms 8088 KB Output is correct
3 Correct 111 ms 8276 KB Output is correct
4 Correct 345 ms 25616 KB Output is correct
5 Correct 204 ms 26044 KB Output is correct
6 Correct 197 ms 26024 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 528 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 6 ms 4036 KB Output is correct
5 Correct 5 ms 3924 KB Output is correct
6 Correct 5 ms 3932 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 103 ms 8216 KB Output is correct
9 Correct 114 ms 8272 KB Output is correct
10 Correct 366 ms 25428 KB Output is correct
11 Correct 201 ms 26028 KB Output is correct
12 Correct 209 ms 26156 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 116 ms 8036 KB Output is correct
15 Correct 27 ms 5208 KB Output is correct
16 Correct 513 ms 25724 KB Output is correct
17 Correct 212 ms 25680 KB Output is correct
18 Correct 210 ms 25848 KB Output is correct

Subtask #4
0 / 39.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 7 ms 3932 KB Output is correct
5 Correct 5 ms 3932 KB Output is correct
6 Correct 5 ms 3932 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 99 ms 8156 KB Output is correct
9 Correct 113 ms 8504 KB Output is correct
10 Correct 374 ms 25428 KB Output is correct
11 Correct 201 ms 26136 KB Output is correct
12 Correct 231 ms 26096 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 108 ms 8016 KB Output is correct
15 Correct 27 ms 5212 KB Output is correct
16 Correct 484 ms 25680 KB Output is correct
17 Correct 207 ms 25840 KB Output is correct
18 Correct 249 ms 25680 KB Output is correct
19 Runtime error 308 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -