oj.uz

Submission #742058

# Submission time Handle Problem Language Result Execution time Memory
742058 2023-05-15T13:37:40 Z angels Wall (IOI14_wall) C++14
100 / 100
 640 ms 74608 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2000010;
const int inf = (1 << 30);

int n, q;
int dst[4 * MAXN], ust[4 * MAXN];
int ar[MAXN];
int t, ql, qr, h;

#define left (index << 1)
#define right (left + 1)
#define mid ((l + r) / 2)
void fix(int index) 
{
	int ind = left;
	for (; ind < left + 2; ind++) {

		dst[ind] = min(dst[ind], dst[index]);
		dst[ind] = max(dst[ind], ust[index]);
		ust[ind] = min(ust[ind], dst[index]);
		ust[ind] = max(ust[ind], ust[index]);

	}
}
void update(int index, int l, int r) 
{
	if (l > qr || r < ql) 
	    return;
	if (l >= ql && r <= qr) 
	{
		if (t == 0) 
		{
			dst[index] = min(dst[index], h);
			ust[index] = min(ust[index], h);
	    }
		else 
	    {
			dst[index] = max(dst[index], h);
			ust[index] = max(ust[index], h);
		}
		return;
	}
	fix(index);
	dst[index] = inf;
	ust[index] = 0;
	update(left, l, mid);
	update(right, mid + 1, r);
}
void dfs(int index, int l, int r) 
{
    if (l == r) 
    {
	    ar[l] = ust[index];
	    assert(ust[index] == dst[index]);
    }
    else 
    {
	    fix(index);
	    dfs(left, l, mid);
	    dfs(right, mid + 1, r);
    }
}
#undef left
#undef right
#undef mid

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    q=k;
	//scanf("%d%d", &n, &q);
	for (int i=0; i<q; i++) 
	{
		//scanf("%d%d%d%d", &t, &ql, &qr, &h);
		t=op[i]; ql=left[i]; qr=right[i]; h=height[i];
		t = (t - 1) ^ 1;
		update(1, 0, n - 1);
	}
    dfs(1, 0, n - 1);
    for (int i = 0; i < n; i++) {
        //printf("%d\n", ar[i]);
        finalHeight[i]=ar[i];
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 7 ms 852 KB Output is correct
5 Correct 5 ms 852 KB Output is correct
6 Correct 5 ms 852 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 151 ms 13960 KB Output is correct
3 Correct 140 ms 8056 KB Output is correct
4 Correct 439 ms 17704 KB Output is correct
5 Correct 264 ms 18768 KB Output is correct
6 Correct 257 ms 17208 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 7 ms 780 KB Output is correct
5 Correct 5 ms 876 KB Output is correct
6 Correct 5 ms 880 KB Output is correct
7 Correct 3 ms 212 KB Output is correct
8 Correct 143 ms 12432 KB Output is correct
9 Correct 204 ms 8052 KB Output is correct
10 Correct 445 ms 17760 KB Output is correct
11 Correct 296 ms 18728 KB Output is correct
12 Correct 295 ms 17240 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 153 ms 12480 KB Output is correct
15 Correct 33 ms 1964 KB Output is correct
16 Correct 403 ms 17984 KB Output is correct
17 Correct 276 ms 17448 KB Output is correct
18 Correct 293 ms 17384 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 368 KB Output is correct
4 Correct 7 ms 852 KB Output is correct
5 Correct 5 ms 824 KB Output is correct
6 Correct 6 ms 828 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 144 ms 12416 KB Output is correct
9 Correct 149 ms 8136 KB Output is correct
10 Correct 421 ms 17696 KB Output is correct
11 Correct 303 ms 18780 KB Output is correct
12 Correct 318 ms 17232 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 137 ms 12500 KB Output is correct
15 Correct 24 ms 2004 KB Output is correct
16 Correct 465 ms 17916 KB Output is correct
17 Correct 262 ms 17508 KB Output is correct
18 Correct 252 ms 17484 KB Output is correct
19 Correct 603 ms 74224 KB Output is correct
20 Correct 607 ms 71920 KB Output is correct
21 Correct 621 ms 74248 KB Output is correct
22 Correct 614 ms 71872 KB Output is correct
23 Correct 640 ms 71900 KB Output is correct
24 Correct 605 ms 72008 KB Output is correct
25 Correct 635 ms 71828 KB Output is correct
26 Correct 615 ms 74348 KB Output is correct
27 Correct 629 ms 74608 KB Output is correct
28 Correct 614 ms 71848 KB Output is correct
29 Correct 609 ms 71916 KB Output is correct
30 Correct 622 ms 71984 KB Output is correct