oj.uz

Submission #952212

# Submission time Handle Problem Language Result Execution time Memory
952212 2024-03-23T09:51:39 Z SmuggingSpun Wall (IOI14_wall) C++14
100 / 100
 463 ms 99412 KB 
#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
template<class T>void maximize(T& a, T b){
	if(a < b){
		a = b;
	}
}
template<class T>void minimize(T& a, T b){
	if(a > b){
		a = b;
	}
}
const int lim = 2e6 + 5;
const int INF = 2e9;
pair<int, int>st[lim << 2];
void solve(int id, int l, int r, int cur, int* ans){
	maximize(cur, st[id].first);
	minimize(cur, st[id].second);
	if(l == r){
		ans[l] = cur;
	}
	else{
		int m = (l + r) >> 1;
		solve(id << 1, l, m, cur, ans);
		solve(id << 1 | 1, m + 1, r, cur, ans);
	}
}
void update(int id, int l, int r, int cur, int u, int v, bool is_maximize){
	if(l > v || r < u){
		return;
	}
	maximize(cur, st[id].first);
	minimize(cur, st[id].second);
	if(u <= l && v >= r){
		if(is_maximize){
			st[id].first = cur;
		}
		else{
			st[id].second = cur;
		}
		return;
	}
	int m = (l + r) >> 1;
	update(id << 1, l, m, cur, u, v, is_maximize);
	update(id << 1 | 1, m + 1, r, cur, u, v, is_maximize);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	for(int i = n << 2; i > 0; i--){
		st[i] = make_pair(0, INF);
	}
	for(int i = k - 1; i > -1; i--){
		update(1, 0, n - 1, height[i], left[i], right[i], op[i] == 1);
	}
	solve(1, 0, n - 1, 0, finalHeight);
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 1 ms 504 KB Output is correct
4 Correct 4 ms 2760 KB Output is correct
5 Correct 4 ms 2904 KB Output is correct
6 Correct 4 ms 2756 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 115 ms 13832 KB Output is correct
3 Correct 143 ms 8564 KB Output is correct
4 Correct 265 ms 22608 KB Output is correct
5 Correct 203 ms 23724 KB Output is correct
6 Correct 192 ms 22164 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 4 ms 2692 KB Output is correct
5 Correct 3 ms 2908 KB Output is correct
6 Correct 3 ms 2904 KB Output is correct
7 Correct 0 ms 444 KB Output is correct
8 Correct 110 ms 13916 KB Output is correct
9 Correct 104 ms 9568 KB Output is correct
10 Correct 288 ms 22748 KB Output is correct
11 Correct 191 ms 23840 KB Output is correct
12 Correct 187 ms 22016 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 131 ms 14016 KB Output is correct
15 Correct 16 ms 3672 KB Output is correct
16 Correct 266 ms 22768 KB Output is correct
17 Correct 202 ms 22348 KB Output is correct
18 Correct 187 ms 22352 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 2 ms 452 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 4 ms 2908 KB Output is correct
5 Correct 4 ms 2908 KB Output is correct
6 Correct 4 ms 2908 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 114 ms 13960 KB Output is correct
9 Correct 104 ms 9672 KB Output is correct
10 Correct 271 ms 22612 KB Output is correct
11 Correct 205 ms 23760 KB Output is correct
12 Correct 187 ms 21996 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 111 ms 13868 KB Output is correct
15 Correct 17 ms 3672 KB Output is correct
16 Correct 275 ms 23032 KB Output is correct
17 Correct 209 ms 22344 KB Output is correct
18 Correct 192 ms 22192 KB Output is correct
19 Correct 438 ms 99392 KB Output is correct
20 Correct 439 ms 96728 KB Output is correct
21 Correct 442 ms 99412 KB Output is correct
22 Correct 463 ms 96868 KB Output is correct
23 Correct 420 ms 96940 KB Output is correct
24 Correct 427 ms 96704 KB Output is correct
25 Correct 433 ms 96768 KB Output is correct
26 Correct 418 ms 99404 KB Output is correct
27 Correct 415 ms 99264 KB Output is correct
28 Correct 412 ms 96852 KB Output is correct
29 Correct 422 ms 96936 KB Output is correct
30 Correct 456 ms 96932 KB Output is correct