oj.uz

Submission #1014086

# Submission time Handle Problem Language Result Execution time Memory
1014086 2024-07-04T10:35:31 Z DorostWef Wall (IOI14_wall) C++17
61 / 100
 487 ms 90960 KB 
#include "wall.h"
#include <bits/stdc++.h>

using namespace std;
#define F first
#define S second

const int N = 500012, SegN = (1 << 20), INF = 1e7 + 190; 
pair <int, int> seg[SegN];
vector <int> s[N], e[N]; 
pair <int, int> p[N];
int kk = 0;

void build (int v = 1, int tl = 0, int tr = kk - 1) {
	seg[v] = {INF, -INF};
	if (tl != tr) {
		int mid = (tl + tr) >> 1;
		build (v << 1, tl, mid);
		build (v << 1 | 1, mid + 1, tr);
	}
}

pair <int, int> Merge (pair <int, int> p, pair <int, int> q) {
	pair <int, int> w;
	if (q.F >= p.F)
		w = p;
	else if (q.F <= p.S) {
		w = {q.F, q.F};
	} else {
		w = {q.F, p.S};
	}
	w.S = max (w.S, q.S);
	if (w.F <= w.S)
		w = {w.S, w.S};
	return w;
}

void upd (int i, int a, int b, int v = 1, int tl = 0, int tr = kk - 1) {
	if (tl == tr) {
		seg[v].F = a;
		seg[v].S = b;
		return;
	}
	int mid = (tl + tr) >> 1;
	if (i <= mid)
		upd (i, a, b, v << 1, tl, mid);
	else
		upd (i, a, b, v << 1 | 1, mid + 1, tr);
	seg[v] = Merge (seg[v << 1], seg[v << 1 | 1]);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	kk = k;
	build();
	for (int i = 0; i < k; i++) {
		s[left[i]].push_back(i);
		e[right[i]].push_back(i);
		if (op[i] == 1) {
			p[i].S = height[i];
			p[i].F = INF;
		} else {
			p[i].F = height[i];
			p[i].S = -INF;
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j : s[i]) {
			upd (j, p[j].F, p[j].S);
		}
		int x = 0;
		x = min (x, seg[1].F);
		x = max (x, seg[1].S);
		finalHeight[i] = x;
		for (int j : e[i]) {
			upd (j, INF, -INF);
		}
	}
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 23900 KB Output is correct
2 Correct 11 ms 24156 KB Output is correct
3 Correct 10 ms 24080 KB Output is correct
4 Correct 13 ms 24564 KB Output is correct
5 Correct 12 ms 24460 KB Output is correct
6 Correct 14 ms 24488 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23900 KB Output is correct
2 Correct 210 ms 53688 KB Output is correct
3 Correct 141 ms 40008 KB Output is correct
4 Correct 444 ms 63320 KB Output is correct
5 Correct 249 ms 62284 KB Output is correct
6 Correct 277 ms 60356 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23900 KB Output is correct
2 Correct 11 ms 24240 KB Output is correct
3 Correct 10 ms 23896 KB Output is correct
4 Correct 12 ms 24412 KB Output is correct
5 Correct 12 ms 24408 KB Output is correct
6 Correct 12 ms 24412 KB Output is correct
7 Correct 9 ms 23800 KB Output is correct
8 Correct 224 ms 53688 KB Output is correct
9 Correct 142 ms 40012 KB Output is correct
10 Correct 396 ms 63508 KB Output is correct
11 Correct 255 ms 62292 KB Output is correct
12 Correct 255 ms 60240 KB Output is correct
13 Correct 9 ms 23896 KB Output is correct
14 Correct 227 ms 53620 KB Output is correct
15 Correct 31 ms 26452 KB Output is correct
16 Correct 396 ms 63572 KB Output is correct
17 Correct 281 ms 60500 KB Output is correct
18 Correct 253 ms 60228 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 23900 KB Output is correct
2 Correct 11 ms 24408 KB Output is correct
3 Correct 10 ms 23900 KB Output is correct
4 Correct 12 ms 24596 KB Output is correct
5 Correct 11 ms 24412 KB Output is correct
6 Correct 12 ms 24400 KB Output is correct
7 Correct 9 ms 23688 KB Output is correct
8 Correct 203 ms 53684 KB Output is correct
9 Correct 142 ms 40024 KB Output is correct
10 Correct 401 ms 63312 KB Output is correct
11 Correct 241 ms 62292 KB Output is correct
12 Correct 256 ms 60416 KB Output is correct
13 Correct 9 ms 23900 KB Output is correct
14 Correct 227 ms 53688 KB Output is correct
15 Correct 30 ms 26608 KB Output is correct
16 Correct 487 ms 63568 KB Output is correct
17 Correct 281 ms 60480 KB Output is correct
18 Correct 275 ms 60240 KB Output is correct
19 Runtime error 138 ms 90960 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -