oj.uz

Submission #779128

# Submission time Handle Problem Language Result Execution time Memory
779128 2023-07-11T08:09:29 Z NothingXD Wall (IOI14_wall) C++17
100 / 100
 730 ms 77356 KB 
#include "wall.h"
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef double ld;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef complex<double> point;

void debug_out(){cerr << endl;}

template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
	cerr << H << ' ';
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)

const int maxn = 2e6 + 10;
const int inf = 1e9;

int n, k, ans[maxn];
pii seg[maxn << 2];

void shift(int v, int l, int r);

void change(int v, int l, int r, int ql, int qr, pii val){
	if (qr <= l || r <= ql) return;
	if (ql <= l && r <= qr){
		if (val.F > seg[v].S) seg[v].S = val.F;
		else if (val.S < seg[v].F) seg[v].F = val.S;
		seg[v].F = max(seg[v].F, val.F);
		seg[v].S = min(seg[v].S, val.S);
		return;
	}
	shift(v, l, r);
	int mid = (l + r) >> 1;
	change(v << 1, l, mid, ql, qr, val);
	change(v << 1 | 1, mid, r, ql, qr, val);
	seg[v].F = min(seg[v << 1].F, seg[v << 1 | 1].F);
	seg[v].S = max(seg[v << 1].S, seg[v << 1 | 1].S);
}

void solve(int v, int l, int r){
	if (l + 1 == r){
		ans[l] = seg[v].F;
		return;
	}
	shift(v, l, r);
	int mid = (l + r) >> 1;
	solve(v << 1, l, mid);
	solve(v << 1 | 1, mid, r);
}

void shift(int v, int l, int r){
	int mid = (l + r) >> 1;
	change(v << 1, l, mid, l, mid, seg[v]);
	change(v << 1 | 1, mid, r, mid, r, seg[v]);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	for (int i = 0; i < k; i++){
		right[i]++;
		if (op[i] == 1){
			change(1, 0, n, left[i], right[i], MP(height[i], inf));
		}
		else{
			change(1, 0, n, left[i], right[i], MP(-inf, height[i]));
		}
	}
	solve(1, 0, n);
	for (int i = 0; i < n; i++) finalHeight[i] = ans[i];
	return;
}

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 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 5 ms 764 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 0 ms 212 KB Output is correct
2 Correct 104 ms 8496 KB Output is correct
3 Correct 159 ms 4428 KB Output is correct
4 Correct 445 ms 11220 KB Output is correct
5 Correct 282 ms 21836 KB Output is correct
6 Correct 278 ms 20156 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 5 ms 852 KB Output is correct
5 Correct 5 ms 832 KB Output is correct
6 Correct 5 ms 764 KB Output is correct
7 Correct 1 ms 308 KB Output is correct
8 Correct 103 ms 13908 KB Output is correct
9 Correct 175 ms 8012 KB Output is correct
10 Correct 452 ms 20740 KB Output is correct
11 Correct 297 ms 21752 KB Output is correct
12 Correct 279 ms 20144 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 107 ms 13912 KB Output is correct
15 Correct 29 ms 1992 KB Output is correct
16 Correct 492 ms 21020 KB Output is correct
17 Correct 285 ms 20452 KB Output is correct
18 Correct 298 ms 20368 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 5 ms 852 KB Output is correct
5 Correct 5 ms 852 KB Output is correct
6 Correct 5 ms 852 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 103 ms 13872 KB Output is correct
9 Correct 156 ms 8032 KB Output is correct
10 Correct 448 ms 20688 KB Output is correct
11 Correct 277 ms 21752 KB Output is correct
12 Correct 281 ms 20188 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 106 ms 13896 KB Output is correct
15 Correct 27 ms 1984 KB Output is correct
16 Correct 486 ms 21032 KB Output is correct
17 Correct 298 ms 20444 KB Output is correct
18 Correct 291 ms 20376 KB Output is correct
19 Correct 668 ms 77316 KB Output is correct
20 Correct 665 ms 74892 KB Output is correct
21 Correct 662 ms 77300 KB Output is correct
22 Correct 730 ms 74776 KB Output is correct
23 Correct 690 ms 74960 KB Output is correct
24 Correct 674 ms 74872 KB Output is correct
25 Correct 655 ms 74772 KB Output is correct
26 Correct 651 ms 77256 KB Output is correct
27 Correct 690 ms 77356 KB Output is correct
28 Correct 709 ms 74748 KB Output is correct
29 Correct 691 ms 74736 KB Output is correct
30 Correct 647 ms 74800 KB Output is correct