oj.uz

Submission #283105

# Submission time Handle Problem Language Result Execution time Memory
283105 2020-08-25T10:02:52 Z peijar Wall (IOI14_wall) C++17
100 / 100
 1048 ms 110456 KB 
#include <bits/stdc++.h>
#include "wall.h"
using namespace std;

#define SZ(v) ((int)(v).size())
using ll = long long;

const int MAXN = 8e6;

int li[MAXN], ri[MAXN];
int lazyMin[MAXN], lazyMax[MAXN];
int val[MAXN];

void buildTree(int node, int l, int r)
{
	li[node] = l, ri[node] = r;

	lazyMin[node] = 1e9;
	lazyMax[node] = 0;
	if (l == r)
		return ;
	buildTree(2*node+1, l, (l+r)/2);
	buildTree(2*node+2, (l+r)/2+1, r);
}

void changeMax(int node, int v)
{
	lazyMax[node] = max(lazyMax[node], v);
	lazyMin[node] = max(lazyMin[node], v);
}

void changeMin(int node, int v)
{
	lazyMin[node] = min(lazyMin[node], v);
	lazyMax[node] = min(lazyMax[node], v);
}

void push(int node)
{
	if (li[node] == ri[node])
		val[li[node]] = min(lazyMin[node], max(lazyMax[node], val[li[node]]));
	else
	{
		changeMax(2*node+1, lazyMax[node]);
		changeMin(2*node+1, lazyMin[node]);
		changeMin(2*node+2, lazyMin[node]);
		changeMax(2*node+2, lazyMax[node]);
	}
	lazyMin[node] = 1e9;
	lazyMax[node] = 0;
}

void updateMax(int node, int lo, int up, int v)
{
	push(node);
	if (li[node] > up or ri[node] < lo)
		return ;
	if (li[node] >= lo and ri[node] <= up)
	{
		changeMax(node, v);
		return;
	}
	updateMax(2*node+1, lo, up, v);
	updateMax(2*node+2, lo, up, v);
}

void updateMin(int node, int lo, int up, int v)
{
	push(node);
	if (li[node] > up or ri[node] < lo)
		return ;
	if (li[node] >= lo and ri[node] <= up)
	{
		changeMin(node, v);
		return;
	}
	updateMin(2*node+1, lo, up, v);
	updateMin(2*node+2, lo, up, v);
}

void recursivePush(int node)
{
	push(node);
	if (li[node] < ri[node])
	{
		recursivePush(2*node+1);
		recursivePush(2*node+2);
	}
}

void buildWall(int n, int k, int op[], int l[], int r[], int v[], int fh[])
{
	buildTree(0, 0, n-1);
	for (int i(0); i < k; ++i)
	{
		if (op[i] == 1)
			updateMax(0, l[i], r[i], v[i]);
		else
			updateMin(0, l[i], r[i], v[i]);
	}
	recursivePush(0);
	for (int i(0); i < n; ++i)
		fh[i] = val[i];
}
/*
int main(void)
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	int nbCol, nbRequetes;
	cin >> nbCol >> nbRequetes;
	buildTree(0, 0, nbCol-1);
	while (nbRequetes--)
	{
		int t, l, r, v;
		cin >> t >> l >> r >> v;
		if (t == 1)
			updateMax(0, l, r, v);
		else
			updateMin(0, l, r, v);
	}
	recursivePush(0);
	for (int i(0); i < nbCol; ++i)
		cout << val[i] << '\n';
}*/

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1152 KB Output is correct
5 Correct 7 ms 1152 KB Output is correct
6 Correct 7 ms 1152 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 184 ms 13980 KB Output is correct
3 Correct 240 ms 8600 KB Output is correct
4 Correct 746 ms 23032 KB Output is correct
5 Correct 412 ms 23928 KB Output is correct
6 Correct 428 ms 22392 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1204 KB Output is correct
5 Correct 7 ms 1152 KB Output is correct
6 Correct 9 ms 1152 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 172 ms 13956 KB Output is correct
9 Correct 280 ms 8696 KB Output is correct
10 Correct 807 ms 23032 KB Output is correct
11 Correct 432 ms 24056 KB Output is correct
12 Correct 393 ms 22392 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 180 ms 14000 KB Output is correct
15 Correct 38 ms 2680 KB Output is correct
16 Correct 750 ms 23128 KB Output is correct
17 Correct 405 ms 22648 KB Output is correct
18 Correct 400 ms 22648 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 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 1 ms 384 KB Output is correct
8 Correct 175 ms 14072 KB Output is correct
9 Correct 233 ms 8568 KB Output is correct
10 Correct 774 ms 22904 KB Output is correct
11 Correct 478 ms 23900 KB Output is correct
12 Correct 478 ms 22520 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 180 ms 14000 KB Output is correct
15 Correct 45 ms 2680 KB Output is correct
16 Correct 866 ms 23288 KB Output is correct
17 Correct 465 ms 22648 KB Output is correct
18 Correct 412 ms 22648 KB Output is correct
19 Correct 994 ms 110368 KB Output is correct
20 Correct 996 ms 107896 KB Output is correct
21 Correct 993 ms 110456 KB Output is correct
22 Correct 992 ms 107768 KB Output is correct
23 Correct 986 ms 107768 KB Output is correct
24 Correct 980 ms 107856 KB Output is correct
25 Correct 1048 ms 107896 KB Output is correct
26 Correct 1008 ms 110456 KB Output is correct
27 Correct 990 ms 110312 KB Output is correct
28 Correct 996 ms 107696 KB Output is correct
29 Correct 977 ms 108024 KB Output is correct
30 Correct 981 ms 107884 KB Output is correct