oj.uz

Submission #1013842

# Submission time Handle Problem Language Result Execution time Memory
1013842 2024-07-04T06:48:47 Z parsadox2 Wall (IOI14_wall) C++17
24 / 100
 264 ms 21376 KB 
#include <bits/stdc++.h>
#include "wall.h"
using namespace std;

const int N = 2e6 + 10;

int n;

struct SEG{
	int L[N << 2] , R[N << 2];
	void Build(int node = 1 , int nl = 0 , int nr = n)
	{
		L[node] = 0;
		R[node] = N;
		if(nr - nl == 1)
			return;
		int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
		Build(lc , nl , mid);  Build(rc , mid , nr);
	}
	void Shift(int node , int lc , int rc)
	{
		L[lc] = max(L[lc] , L[node]);
		R[lc] = min(R[lc] , R[node]);
		L[rc] = max(L[rc] , L[node]);
		R[rc] = min(R[rc] , R[node]);
		if(R[lc] < L[lc])
		{
			if(R[lc] == R[node])
				L[lc] = R[node];
			else
				R[lc] = L[node];
		}
		if(R[rc] < L[rc])
		{
			if(R[rc] == R[node])
				L[rc] = R[node];
			else
				R[lc] = L[node];
		}
		L[node] = 0;
		R[node] = N;
	}
	void Min(int l , int r , int val , int node = 1 , int nl = 0 , int nr = n)
	{
		if(r <= nl || nr <= l)
			return;
		if(l <= nl && nr <= r)
		{
			R[node] = min(R[node] , val);
			if(R[node] < L[node])
				L[node] = R[node];
			return;
		}
		int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
		Shift(node , lc , rc);
		Min(l , r , val , lc , nl , mid);
		Min(l , r , val , rc , mid , nr);
	}
	void Max(int l , int r , int val , int node = 1 , int nl = 0 , int nr = n)
	{
		if(r <= nl || nr <= l)
			return;
		if(l <= nl && nr <= r)
		{
			L[node] = max(L[node] , val);
			if(R[node] < L[node])
				R[node] = L[node];
			return;
		}
		int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
		Shift(node , lc , rc);
		Max(l , r , val , lc , nl , mid);
		Max(l , r , val , rc , mid , nr);
	}
	int Get(int id , int node = 1 , int nl = 0 , int nr = n)
	{
		if(nr - nl == 1)
			return L[node];
		int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
		Shift(node , lc , rc);
		if(id < mid)
			return Get(id , lc , nl , mid);
		else
			return Get(id , rc , mid , nr);
	}
	void Debug(int node = 1 , int nl = 0 , int nr = n)
	{
		cout << node << " " << nl << " " << nr << " : " << L[node] << " " << R[node] << endl;
		if(nr - nl == 1)
			return;
		int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
		Debug(lc , nl , mid);
		Debug(rc , mid , nr);
	}
} seg;

void buildWall(int nn, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	n = nn;
	seg.Build();
	for(int i = 0 ; i < k ; i++)
	{
		if(op[i] == 1)
			seg.Max(left[i] , right[i] + 1 , height[i]);
		else
			seg.Min(left[i] , right[i] + 1 , height[i]);
		//seg.Debug();
		//cout << endl;
	}
	for(int i = 0 ; i < n ; i++)
		finalHeight[i] = seg.Get(i);
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 80 ms 13944 KB Output is correct
3 Correct 97 ms 8020 KB Output is correct
4 Correct 264 ms 20304 KB Output is correct
5 Correct 173 ms 21376 KB Output is correct
6 Correct 168 ms 19796 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Incorrect 1 ms 520 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 584 KB Output is correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -