oj.uz

Submission #640215

# Submission time Handle Problem Language Result Execution time Memory
640215 2022-09-14T02:12:05 Z ymm Wall (IOI14_wall) C++17
100 / 100
 700 ms 60568 KB 
#include "wall.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

static const int N = 1<<21;
static int mn[N<<1];
static int mx[N<<1];

static inline void ppg(int i)
{
	if (mn[i] == mx[i]) {
		mn[2*i+1] = mx[2*i+1] = mn[i];
		mn[2*i+2] = mx[2*i+2] = mn[i];
	}
}

static inline void up(int i)
{
	mn[i] = min(mn[2*i+1], mn[2*i+2]);
	mx[i] = max(mx[2*i+1], mx[2*i+2]);
}

static void inc(int l, int r, int h, int i=0, int b=0, int e=N)
{
	if (l <= b && e <= r && mx[i] <= h) {
		mn[i] = mx[i] = h;
		return;
	}
	if (r <= b || e <= l || mn[i] >= h)
		return;
	ppg(i);
	inc(l, r, h, 2*i+1, b, (b+e)/2);
	inc(l, r, h, 2*i+2, (b+e)/2, e);
	up(i);
}

static void dec(int l, int r, int h, int i=0, int b=0, int e=N)
{
	if (l <= b && e <= r && mn[i] >= h) {
		mn[i] = mx[i] = h;
		return;
	}
	if (r <= b || e <= l || mx[i] <= h)
		return;
	ppg(i);
	dec(l, r, h, 2*i+1, b, (b+e)/2);
	dec(l, r, h, 2*i+2, (b+e)/2, e);
	up(i);
}

static int get(int p, int i=0, int b=0, int e=N)
{
	if (mn[i] == mx[i])
		return mn[i];
	if (p < (b+e)/2)
		return get(p, 2*i+1, b, (b+e)/2);
	else
		return get(p, 2*i+2, (b+e)/2, e);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
	Loop (i,0,k) {
		if (op[i] == 1)
			inc(left[i], right[i]+1, height[i]);
		else
			dec(left[i], right[i]+1, height[i]);
	}
	Loop (i,0,n)
		finalHeight[i] = get(i);
}

Subtask #1
8.0 / 8.0

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

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 432 KB Output is correct
2 Correct 210 ms 9264 KB Output is correct
3 Correct 76 ms 5068 KB Output is correct
4 Correct 148 ms 10956 KB Output is correct
5 Correct 174 ms 10480 KB Output is correct
6 Correct 197 ms 10356 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 4 ms 596 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 5 ms 796 KB Output is correct
5 Correct 6 ms 832 KB Output is correct
6 Correct 5 ms 724 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 226 ms 9288 KB Output is correct
9 Correct 77 ms 5024 KB Output is correct
10 Correct 149 ms 10904 KB Output is correct
11 Correct 175 ms 10360 KB Output is correct
12 Correct 200 ms 10416 KB Output is correct
13 Correct 1 ms 436 KB Output is correct
14 Correct 209 ms 9352 KB Output is correct
15 Correct 24 ms 1864 KB Output is correct
16 Correct 378 ms 11668 KB Output is correct
17 Correct 275 ms 11836 KB Output is correct
18 Correct 279 ms 11724 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 432 KB Output is correct
2 Correct 3 ms 572 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 5 ms 724 KB Output is correct
5 Correct 5 ms 724 KB Output is correct
6 Correct 5 ms 816 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 226 ms 9292 KB Output is correct
9 Correct 78 ms 5064 KB Output is correct
10 Correct 149 ms 10936 KB Output is correct
11 Correct 174 ms 10388 KB Output is correct
12 Correct 204 ms 10380 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 211 ms 9164 KB Output is correct
15 Correct 24 ms 1868 KB Output is correct
16 Correct 372 ms 11500 KB Output is correct
17 Correct 287 ms 11348 KB Output is correct
18 Correct 307 ms 11328 KB Output is correct
19 Correct 643 ms 50600 KB Output is correct
20 Correct 637 ms 57876 KB Output is correct
21 Correct 652 ms 60568 KB Output is correct
22 Correct 654 ms 57748 KB Output is correct
23 Correct 642 ms 57840 KB Output is correct
24 Correct 681 ms 57916 KB Output is correct
25 Correct 641 ms 57724 KB Output is correct
26 Correct 681 ms 60388 KB Output is correct
27 Correct 700 ms 60328 KB Output is correct
28 Correct 634 ms 57964 KB Output is correct
29 Correct 633 ms 57796 KB Output is correct
30 Correct 638 ms 57760 KB Output is correct