oj.uz

Submission #1013854

# Submission time Handle Problem Language Result Execution time Memory
1013854 2024-07-04T06:55:55 Z parsadox2 Wall (IOI14_wall) C++17
100 / 100
 560 ms 69528 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[rc] = 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
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 4 ms 908 KB Output is correct
5 Correct 4 ms 860 KB Output is correct
6 Correct 3 ms 860 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 78 ms 14080 KB Output is correct
3 Correct 121 ms 8020 KB Output is correct
4 Correct 284 ms 20332 KB Output is correct
5 Correct 190 ms 21328 KB Output is correct
6 Correct 184 ms 19792 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 4 ms 912 KB Output is correct
5 Correct 3 ms 856 KB Output is correct
6 Correct 3 ms 856 KB Output is correct
7 Correct 0 ms 600 KB Output is correct
8 Correct 126 ms 14056 KB Output is correct
9 Correct 106 ms 8016 KB Output is correct
10 Correct 255 ms 20456 KB Output is correct
11 Correct 178 ms 21444 KB Output is correct
12 Correct 151 ms 19796 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 91 ms 13904 KB Output is correct
15 Correct 19 ms 2160 KB Output is correct
16 Correct 388 ms 20592 KB Output is correct
17 Correct 178 ms 20052 KB Output is correct
18 Correct 166 ms 20052 KB Output is correct

Subtask #4
39.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 4 ms 860 KB Output is correct
5 Correct 3 ms 860 KB Output is correct
6 Correct 3 ms 860 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 77 ms 13936 KB Output is correct
9 Correct 93 ms 8016 KB Output is correct
10 Correct 248 ms 20604 KB Output is correct
11 Correct 164 ms 21328 KB Output is correct
12 Correct 155 ms 19868 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 76 ms 13876 KB Output is correct
15 Correct 21 ms 2140 KB Output is correct
16 Correct 354 ms 20540 KB Output is correct
17 Correct 175 ms 20052 KB Output is correct
18 Correct 174 ms 20032 KB Output is correct
19 Correct 543 ms 69460 KB Output is correct
20 Correct 551 ms 66984 KB Output is correct
21 Correct 551 ms 69460 KB Output is correct
22 Correct 526 ms 67152 KB Output is correct
23 Correct 560 ms 67288 KB Output is correct
24 Correct 516 ms 67008 KB Output is correct
25 Correct 549 ms 66900 KB Output is correct
26 Correct 521 ms 69460 KB Output is correct
27 Correct 552 ms 69528 KB Output is correct
28 Correct 559 ms 66900 KB Output is correct
29 Correct 525 ms 67064 KB Output is correct
30 Correct 545 ms 67152 KB Output is correct