oj.uz

Submission #1040792

# Submission time Handle Problem Language Result Execution time Memory
1040792 2024-08-01T09:26:06 Z lovrot Wall (IOI14_wall) C++17
100 / 100
 358 ms 69500 KB 
#include "wall.h"
#include <algorithm>
#include <set>
#include <vector>
#include <cstdio>

#define PB push_back
#define debug(...) //fprintf(stderr, __VA_ARGS__)

using namespace std;

const int LOG = 21;
const int N = 1 << LOG;
const int OO = 0x7FFFFFFF;

struct node {
	int a, b;
	node() : a(0), b(OO) {}
	node(int a, int b) : a(a), b(b) {}
};

node t[2 * N];

void merge(int &a, int &b, int l, int r) { 
	a = min(r, max(l, a));
	b = max(l, min(r, b));
}

void propagate(int u) { 
	merge(t[2 * u].a, t[2 * u].b, t[u].a, t[u].b);
	merge(t[2 * u + 1].a, t[2 * u + 1].b, t[u].a, t[u].b);
	t[u].a = 0;
	t[u].b = OO;
}

void update(int l, int r, int a, int b, int u = 1, int lo = 0, int hi = N) { 
	if(r <= lo || hi <= l) { 
		return;
	}
	if(l <= lo && hi <= r) { 
		merge(t[u].a, t[u].b, a, b);
		return;
	}
	int mi = (lo + hi) / 2;
	propagate(u);
	update(l, r, a, b, 2 * u, lo, mi);
	update(l, r, a, b, 2 * u + 1, mi, hi);
}

void query(int u = 1, int lo = 0, int hi = N) { 
	if(u >= N) { return; }
	int mi = (lo + hi) / 2;
	propagate(u);
	query(2 * u, lo, mi);
	query(2 * u + 1, mi, hi);
}
			
void buildWall(int n, int k, int op[], int lft[], int rgt[], int hgt[], int fnl[]){
	for(int i = 0; i < k; ++i) { 
		int a, b;
		if(op[i] == 1) {
			a = hgt[i];
			b = OO;
		} else {
			a = 0;
			b = hgt[i];
		}
		update(lft[i], rgt[i] + 1, a, b);
	}

	query();

	for(int i = 0; i < n; ++i) { 
		fnl[i] = t[N + i].a;
		debug("%d %d\n", i, fnl[i]);
	}
	return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 33112 KB Output is correct
2 Correct 15 ms 33372 KB Output is correct
3 Correct 14 ms 33312 KB Output is correct
4 Correct 16 ms 33372 KB Output is correct
5 Correct 16 ms 33372 KB Output is correct
6 Correct 16 ms 33444 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 33116 KB Output is correct
2 Correct 165 ms 46688 KB Output is correct
3 Correct 112 ms 40268 KB Output is correct
4 Correct 272 ms 51276 KB Output is correct
5 Correct 185 ms 52308 KB Output is correct
6 Correct 173 ms 50516 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 33112 KB Output is correct
2 Correct 17 ms 33372 KB Output is correct
3 Correct 15 ms 33116 KB Output is correct
4 Correct 23 ms 33260 KB Output is correct
5 Correct 20 ms 33456 KB Output is correct
6 Correct 17 ms 33372 KB Output is correct
7 Correct 14 ms 33116 KB Output is correct
8 Correct 169 ms 46852 KB Output is correct
9 Correct 111 ms 40364 KB Output is correct
10 Correct 272 ms 51248 KB Output is correct
11 Correct 196 ms 52304 KB Output is correct
12 Correct 173 ms 50516 KB Output is correct
13 Correct 14 ms 33116 KB Output is correct
14 Correct 167 ms 46848 KB Output is correct
15 Correct 34 ms 34396 KB Output is correct
16 Correct 275 ms 51536 KB Output is correct
17 Correct 177 ms 50912 KB Output is correct
18 Correct 191 ms 50772 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 33116 KB Output is correct
2 Correct 15 ms 33384 KB Output is correct
3 Correct 14 ms 33112 KB Output is correct
4 Correct 16 ms 33368 KB Output is correct
5 Correct 16 ms 33460 KB Output is correct
6 Correct 16 ms 33456 KB Output is correct
7 Correct 14 ms 33116 KB Output is correct
8 Correct 185 ms 46768 KB Output is correct
9 Correct 111 ms 40352 KB Output is correct
10 Correct 269 ms 51124 KB Output is correct
11 Correct 182 ms 52188 KB Output is correct
12 Correct 175 ms 50512 KB Output is correct
13 Correct 14 ms 33116 KB Output is correct
14 Correct 163 ms 46848 KB Output is correct
15 Correct 29 ms 34388 KB Output is correct
16 Correct 278 ms 51452 KB Output is correct
17 Correct 198 ms 50808 KB Output is correct
18 Correct 179 ms 50768 KB Output is correct
19 Correct 342 ms 69456 KB Output is correct
20 Correct 356 ms 67064 KB Output is correct
21 Correct 357 ms 69500 KB Output is correct
22 Correct 352 ms 66900 KB Output is correct
23 Correct 358 ms 66956 KB Output is correct
24 Correct 341 ms 67016 KB Output is correct
25 Correct 337 ms 67124 KB Output is correct
26 Correct 342 ms 69460 KB Output is correct
27 Correct 343 ms 69460 KB Output is correct
28 Correct 340 ms 67048 KB Output is correct
29 Correct 331 ms 67156 KB Output is correct
30 Correct 330 ms 66900 KB Output is correct