oj.uz

Submission #511281

# Submission time Handle Problem Language Result Execution time Memory
511281 2022-01-15T13:50:34 Z AdamGS Wall (IOI14_wall) C++14
100 / 100
 646 ms 62636 KB 
#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=2e6+7, INF=1e9+7;
int ma[4*LIM], mi[4*LIM], N=1;
void spl(int v) {
	ma[2*v]=min(ma[2*v], ma[v]);
	ma[2*v]=max(ma[2*v], mi[v]);
	ma[2*v+1]=min(ma[2*v+1], ma[v]);
	ma[2*v+1]=max(ma[2*v+1], mi[v]);
	mi[2*v]=max(mi[2*v], mi[v]);
	mi[2*v]=min(mi[2*v], ma[v]);
	mi[2*v+1]=max(mi[2*v+1], mi[v]);
	mi[2*v+1]=min(mi[2*v+1], ma[v]);
	ma[v]=INF;
	mi[v]=-INF;
}
void maxuj(int v, int l, int r, int a, int b, int x) {
	if(b<l || a>r) return;
	if(a<=l && r<=b) {
		ma[v]=max(ma[v], x);
		mi[v]=max(mi[v], x);
		return;
	}
	spl(v);
	int mid=(l+r)/2;
	maxuj(2*v, l, mid, a, b, x);
	maxuj(2*v+1, mid+1, r, a, b, x);
}
void minuj(int v, int l, int r, int a, int b, int x) {
	if(b<l || a>r) return;
	if(a<=l && r<=b) {
		ma[v]=min(ma[v], x);
		mi[v]=min(mi[v], x);
		return;
	}
	spl(v);
	int mid=(l+r)/2;
	minuj(2*v, l, mid, a, b, x);
	minuj(2*v+1, mid+1, r, a, b, x);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	while(N<n) N*=2;
	rep(i, N) {
		ma[i]=INF;
		mi[i]=-INF;
	}
	rep(i, k) {
		if(op[i]==1) maxuj(1, 0, N-1, left[i], right[i], height[i]);
		else minuj(1, 0, N-1, left[i], right[i], height[i]);
	}
	for(int i=1; i<N; ++i) spl(i);
	rep(i, n) finalHeight[i]=ma[N+i];
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 280 KB Output is correct
2 Correct 3 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 6 ms 704 KB Output is correct
5 Correct 4 ms 716 KB Output is correct
6 Correct 4 ms 716 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 158 ms 9660 KB Output is correct
3 Correct 137 ms 4488 KB Output is correct
4 Correct 423 ms 13376 KB Output is correct
5 Correct 252 ms 17092 KB Output is correct
6 Correct 251 ms 13964 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 3 ms 332 KB Output is correct
4 Correct 5 ms 716 KB Output is correct
5 Correct 5 ms 716 KB Output is correct
6 Correct 5 ms 668 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 140 ms 9952 KB Output is correct
9 Correct 142 ms 4924 KB Output is correct
10 Correct 403 ms 13360 KB Output is correct
11 Correct 264 ms 14760 KB Output is correct
12 Correct 251 ms 13124 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 153 ms 9384 KB Output is correct
15 Correct 24 ms 1476 KB Output is correct
16 Correct 393 ms 14432 KB Output is correct
17 Correct 262 ms 14612 KB Output is correct
18 Correct 246 ms 11864 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 1 ms 312 KB Output is correct
4 Correct 4 ms 672 KB Output is correct
5 Correct 4 ms 672 KB Output is correct
6 Correct 4 ms 668 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 156 ms 9328 KB Output is correct
9 Correct 131 ms 5780 KB Output is correct
10 Correct 393 ms 14600 KB Output is correct
11 Correct 270 ms 13356 KB Output is correct
12 Correct 252 ms 13644 KB Output is correct
13 Correct 1 ms 300 KB Output is correct
14 Correct 155 ms 9352 KB Output is correct
15 Correct 22 ms 1420 KB Output is correct
16 Correct 405 ms 13856 KB Output is correct
17 Correct 256 ms 13340 KB Output is correct
18 Correct 270 ms 11984 KB Output is correct
19 Correct 636 ms 62636 KB Output is correct
20 Correct 608 ms 59164 KB Output is correct
21 Correct 591 ms 61932 KB Output is correct
22 Correct 588 ms 57732 KB Output is correct
23 Correct 582 ms 57496 KB Output is correct
24 Correct 612 ms 59636 KB Output is correct
25 Correct 623 ms 57520 KB Output is correct
26 Correct 612 ms 61028 KB Output is correct
27 Correct 646 ms 60072 KB Output is correct
28 Correct 557 ms 60868 KB Output is correct
29 Correct 580 ms 60116 KB Output is correct
30 Correct 611 ms 61176 KB Output is correct