oj.uz

Submission #530160

# Submission time Handle Problem Language Result Execution time Memory
530160 2022-02-24T17:31:35 Z Hanksburger Wall (IOI14_wall) C++17
100 / 100
 545 ms 77476 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
int lazyMax[8000005], lazyMin[8000005];
vector<int> vec;
void build(int i, int l, int r)
{
	lazyMax[i]=-1;
	lazyMin[i]=-1;
	if (l==r)
		return;
	int mid=(l+r)/2;
	build(i*2, l, mid);
	build(i*2+1, mid+1, r);
}
void push(int i, int op, int h)
{
	if (op==1)
	{
		if (lazyMax[i]!=-1)
			lazyMax[i]=max(lazyMax[i], h);
		else
			lazyMax[i]=h;
		if (lazyMin[i]!=-1)
			lazyMin[i]=max(lazyMin[i], h);
	}
	else
	{
		if (lazyMax[i]!=-1)
		lazyMax[i]=min(lazyMax[i], h);
		if (lazyMin[i]!=-1)
			lazyMin[i]=min(lazyMin[i], h);
		else
			lazyMin[i]=h;
	}
}
void update(int i, int l, int r, int op, int ql, int qr, int h)
{
//	cout << "update " << i << ' ' << l << ' ' << r << ' ' << op << ' ' << ql << ' ' << qr << ' ' << h << '\n';
	if (ql<=l && r<=qr)
	{
//		cout << "updated: " << l << "-" << r << " from " << lazyMax[i] << ' ' << lazyMin[i] << " to ";
		push(i, op, h);
//		cout << lazyMax[i] << " " << lazyMin[i] << '\n';
		return;
	}
//	cout << "push " << lazyMax[i] << " and " << lazyMin[i] << " into [" << l << "-" << (l+r)/2 << "] and [" << (l+r)/2+1 << "-" << r << "]" << '\n';
	if (lazyMax[i]!=-1)
	{
		push(i*2, 1, lazyMax[i]);
		push(i*2+1, 1, lazyMax[i]);
		lazyMax[i]=-1;
	}
	if (lazyMin[i]!=-1)
	{
		push(i*2, 2, lazyMin[i]);
		push(i*2+1, 2, lazyMin[i]);
		lazyMin[i]=-1;
	}
	int mid=(l+r)/2;
	if (l<=qr && ql<=mid)
		update(i*2, l, mid, op, ql, qr, h);
	if (mid+1<=qr && ql<=r)
		update(i*2+1, mid+1, r, op, ql, qr, h);
}
void query(int i, int l, int r)
{
//	cout << "query " << i << ' ' << l << ' ' << r << '\n';
	if (l==r)
	{
		vec.push_back(max(0, lazyMax[i]));
		return;
	}
//	cout << "push " << lazyMax[i] << " and " << lazyMin[i] << " into [" << l << "-" << (l+r)/2 << "] and [" << (l+r)/2+1 << "-" << r << "]" << '\n';
	if (lazyMax[i]!=-1)
	{
		push(i*2, 1, lazyMax[i]);
		push(i*2+1, 1, lazyMax[i]);
		lazyMax[i]=-1;
	}
	if (lazyMin[i]!=-1)
	{
		push(i*2, 2, lazyMin[i]);
		push(i*2+1, 2, lazyMin[i]);
		lazyMin[i]=-1;
	}
	int mid=(l+r)/2;
	query(i*2, l, mid);
	query(i*2+1, mid+1, r);
}
void buildWall(int n, int k, int op[], int l[], int r[], int h[], int fh[])
{
	build(1, 0, n-1);
	for (int i=0; i<k; i++)
//	{
		update(1, 0, n-1, op[i], l[i], r[i], h[i]);
//		query(1, 0, n-1);
//		cout << "vec: ";
//		for (int j=0; j<n; j++)
//			cout << vec[j] << ' ';
//		cout << '\n';
//		vec.clear();
//	}
	query(1, 0, n-1);
	for (int i=0; i<n; i++)
		fh[i]=vec[i];
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 2 ms 436 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 6 ms 884 KB Output is correct
5 Correct 4 ms 844 KB Output is correct
6 Correct 4 ms 844 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 136 ms 14020 KB Output is correct
3 Correct 165 ms 8064 KB Output is correct
4 Correct 445 ms 20900 KB Output is correct
5 Correct 214 ms 21868 KB Output is correct
6 Correct 211 ms 20436 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 2 ms 432 KB Output is correct
3 Correct 2 ms 308 KB Output is correct
4 Correct 6 ms 844 KB Output is correct
5 Correct 4 ms 848 KB Output is correct
6 Correct 5 ms 856 KB Output is correct
7 Correct 1 ms 300 KB Output is correct
8 Correct 139 ms 13908 KB Output is correct
9 Correct 165 ms 8164 KB Output is correct
10 Correct 459 ms 20900 KB Output is correct
11 Correct 221 ms 21944 KB Output is correct
12 Correct 208 ms 20264 KB Output is correct
13 Correct 0 ms 304 KB Output is correct
14 Correct 135 ms 13848 KB Output is correct
15 Correct 32 ms 2096 KB Output is correct
16 Correct 544 ms 21192 KB Output is correct
17 Correct 216 ms 20496 KB Output is correct
18 Correct 220 ms 20496 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 2 ms 440 KB Output is correct
3 Correct 1 ms 312 KB Output is correct
4 Correct 6 ms 844 KB Output is correct
5 Correct 4 ms 868 KB Output is correct
6 Correct 5 ms 888 KB Output is correct
7 Correct 0 ms 304 KB Output is correct
8 Correct 155 ms 13968 KB Output is correct
9 Correct 163 ms 8132 KB Output is correct
10 Correct 454 ms 20908 KB Output is correct
11 Correct 216 ms 22000 KB Output is correct
12 Correct 208 ms 20284 KB Output is correct
13 Correct 1 ms 304 KB Output is correct
14 Correct 136 ms 14128 KB Output is correct
15 Correct 31 ms 2176 KB Output is correct
16 Correct 537 ms 21176 KB Output is correct
17 Correct 223 ms 20540 KB Output is correct
18 Correct 207 ms 20456 KB Output is correct
19 Correct 545 ms 77424 KB Output is correct
20 Correct 540 ms 74984 KB Output is correct
21 Correct 536 ms 77476 KB Output is correct
22 Correct 537 ms 74972 KB Output is correct
23 Correct 536 ms 75068 KB Output is correct
24 Correct 543 ms 75012 KB Output is correct
25 Correct 541 ms 74904 KB Output is correct
26 Correct 531 ms 77472 KB Output is correct
27 Correct 531 ms 77372 KB Output is correct
28 Correct 526 ms 74928 KB Output is correct
29 Correct 531 ms 74912 KB Output is correct
30 Correct 539 ms 74924 KB Output is correct