oj.uz

Submission #257394

# Submission time Handle Problem Language Result Execution time Memory
257394 2020-08-04T08:21:41 Z Berted Wall (IOI14_wall) C++14
100 / 100
 1110 ms 102648 KB 
#include "wall.h"
#include <algorithm>
#include <utility>
#include <iostream>
#define pii pair<int, int>
#define fst first
#define snd second

using namespace std;

const int SZ = (1 << 22) + 5;

pii lz[SZ];
pii seg[SZ];

inline void prop(int idx, int L, int R)
{
	if (L <= R)
	{
		if (seg[idx] != lz[idx])
		{
			seg[idx] = lz[idx];
			if (L < R)
			{
				lz[2 * idx].fst = max(lz[2 * idx].fst, lz[idx].fst);
				lz[2 * idx].snd = max(lz[2 * idx].snd, lz[idx].fst);
				lz[2 * idx].fst = min(lz[2 * idx].fst, lz[idx].snd);
				lz[2 * idx].snd = min(lz[2 * idx].snd, lz[idx].snd);
				lz[2 * idx + 1].fst = max(lz[2 * idx + 1].fst, lz[idx].fst);
				lz[2 * idx + 1].snd = max(lz[2 * idx + 1].snd, lz[idx].fst);
				lz[2 * idx + 1].fst = min(lz[2 * idx + 1].fst, lz[idx].snd);
				lz[2 * idx + 1].snd = min(lz[2 * idx + 1].snd, lz[idx].snd);
			}
		}
	}
}

inline void merge(pii& p, const pii &l, const pii &r)
{
	p = make_pair(min(l.fst, r.fst), max(l.snd, r.snd));
}

void upd(int idx, int L, int R, int l, int r, int t, int v)
{
	prop(idx, L, R);
	if (l <= r)
	{
		if (L == l && R == r)
		{
			if (t == 1)
			{
				lz[idx].fst = max(v, lz[idx].fst);
				lz[idx].snd = max(v, lz[idx].snd);
			}
			else
			{
				lz[idx].fst = min(v, lz[idx].fst);
				lz[idx].snd = min(v, lz[idx].snd);
			}
			prop(idx, L, R);
		}
		else
		{
			int M = L + R >> 1;
			upd(2 * idx, L, M, l, min(M, r), t, v);
			upd(2 * idx + 1, M + 1, R, max(M + 1, l), r, t, v);
			merge(seg[idx], seg[2 * idx], seg[2 * idx + 1]);
			lz[idx] = seg[idx];
		}
	}
	//cout << "UPD [" << L << ", " << R << "] " << seg[idx].fst << ", " << seg[idx].snd << ", T = " << t << ", V = " << v << "\n";
}

inline int qry(int idx, int L, int R, int x)
{
	prop(idx, L, R);
	if (L == x && R == x) {return seg[idx].fst;}
	else
	{
		int M = L + R >> 1;
		if (x <= M) {return qry(2 * idx, L, M, x);}
		else {return qry(2 * idx + 1, M + 1, R, x);}
	}
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	for (int i = 0; i < k; i++)
	{
		upd(1, 0, n - 1, left[i], right[i], op[i], height[i]);	
	}
	for (int i = 0; i < n; i++)
	{
		finalHeight[i] = qry(1, 0, n - 1, i);
	}
	return;
}

Compilation message

wall.cpp: In function 'void upd(int, int, int, int, int, int, int)':
wall.cpp:64:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    int M = L + R >> 1;
            ~~^~~
wall.cpp: In function 'int qry(int, int, int, int)':
wall.cpp:80:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int M = L + R >> 1;
           ~~^~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 9 ms 1152 KB Output is correct
5 Correct 7 ms 1152 KB Output is correct
6 Correct 6 ms 1152 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 184 ms 14056 KB Output is correct
3 Correct 205 ms 8608 KB Output is correct
4 Correct 599 ms 22568 KB Output is correct
5 Correct 365 ms 23544 KB Output is correct
6 Correct 366 ms 22008 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 9 ms 1152 KB Output is correct
5 Correct 7 ms 1152 KB Output is correct
6 Correct 7 ms 1152 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 185 ms 13944 KB Output is correct
9 Correct 201 ms 8548 KB Output is correct
10 Correct 557 ms 22520 KB Output is correct
11 Correct 368 ms 23544 KB Output is correct
12 Correct 346 ms 22108 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 185 ms 14072 KB Output is correct
15 Correct 45 ms 2552 KB Output is correct
16 Correct 760 ms 22776 KB Output is correct
17 Correct 374 ms 22268 KB Output is correct
18 Correct 366 ms 22192 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 8 ms 1024 KB Output is correct
5 Correct 7 ms 1152 KB Output is correct
6 Correct 7 ms 1152 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 182 ms 14056 KB Output is correct
9 Correct 217 ms 8572 KB Output is correct
10 Correct 610 ms 22648 KB Output is correct
11 Correct 376 ms 23544 KB Output is correct
12 Correct 353 ms 22140 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 181 ms 13944 KB Output is correct
15 Correct 45 ms 2552 KB Output is correct
16 Correct 767 ms 22736 KB Output is correct
17 Correct 377 ms 22136 KB Output is correct
18 Correct 365 ms 22268 KB Output is correct
19 Correct 1066 ms 102520 KB Output is correct
20 Correct 1012 ms 83704 KB Output is correct
21 Correct 1081 ms 102648 KB Output is correct
22 Correct 1110 ms 83832 KB Output is correct
23 Correct 1014 ms 83652 KB Output is correct
24 Correct 1034 ms 83832 KB Output is correct
25 Correct 1038 ms 83704 KB Output is correct
26 Correct 1060 ms 102472 KB Output is correct
27 Correct 1055 ms 102576 KB Output is correct
28 Correct 1030 ms 83832 KB Output is correct
29 Correct 1036 ms 83840 KB Output is correct
30 Correct 1028 ms 83772 KB Output is correct