oj.uz

Submission #236114

# Submission time Handle Problem Language Result Execution time Memory
236114 2020-05-31T08:37:29 Z crossing0ver Wall (IOI14_wall) C++17
100 / 100
 820 ms 133772 KB 
#include<bits/stdc++.h>
#include "wall.h"
using namespace std;
const int N = 2E6;
int t[4*N],lazy[4*N][2],l,r,val;// min h, max h
bool type;

void push(int v,int tl,int tr) {
	if (lazy[v][0]) {
		if (lazy[v*2][0] < lazy[v][0]){
			lazy[v*2][0]  = lazy[v][0];
			if (t[v*2] < lazy[v][0]) t[v*2] = lazy[v][0];
		}
		if (lazy[v*2|1][0] < lazy[v][0]) {
			lazy[v*2|1][0] = lazy[v][0];
			if (t[v*2|1] < lazy[v][0]) t[v*2|1] = lazy[v][0];
		}
		if (lazy[v*2][0] > lazy[v*2][1]) {
		lazy[v*2][1] = lazy[v*2][0];
		}
		if (lazy[v*2|1][0] > lazy[v*2|1][1] ) {
		lazy[v*2|1][1] = lazy[v*2|1][0]; 
		}
		lazy[v][0] = 0;
	}
	if (lazy[v][1] != 1e9) {
		if (lazy[v*2][1] > lazy[v][1]) {
			lazy[v*2][1] = lazy[v][1];
			lazy[v*2][0] = min (lazy[v*2][0],lazy[v*2][1]);
			if (t[v*2] > lazy[v][1]) t[v*2] = lazy[v][1];
		}
		if (lazy[v*2|1][1] > lazy[v][1]) {
			lazy[v*2|1][1]  = lazy[v][1];
			lazy[v*2|1][0] = min (lazy[v*2|1][0],lazy[v*2|1][1]);
			if (t[v*2|1] > lazy[v][1]) t[v*2|1] = lazy[v][1];
		}
  		lazy[v][1] = 1e9;
	}
}
void upd (int v,int tl,int tr) {
	if (l > tr || r < tl) return;
	if (tl >= l && tr <= r) {
		if (type == 0) {
			if (lazy[v][0] >= val) return;
			t[v] = max (t[v],val);
			lazy[v][0] = max (lazy[v][0],val);
			if (lazy[v][1] < lazy[v][0]) {
				lazy[v][1] = lazy[v][0];
			}
		}
		else {
			if (lazy[v][1] <= val) return;
			lazy[v][1] = val;
			if (lazy[v][0] > lazy[v][1]) {
				lazy[v][0] = lazy[v][1];
			}
			t[v] = min(t[v],lazy[v][1]);
		}
		return;
	}
	push (v,tl,tr);
	int tm = (tl + tr)/2;
	upd (v*2,tl,tm);
	upd (v*2|1,tm+1,tr);
	t[v] = min(t[v*2],t[v*2|1]);
}
int A[N];
void get (int v,int tl,int tr) {
	if (tl == tr) A[tl] = t[v];
	else {
		int tm = (tl + tr)/2;
		push(v,tl,tr);
		get(v*2,tl,tm);
		get(v*2+1,tm+1,tr);
	} 
}
void buildWall(int n,int k,int op[],int left1[],int right1[],int height[],int finalHeight[]) {
	for (int i = 0; i < 4*N; i++) lazy[i][1] = 1e9,t[i] = 1,lazy[i][0] = 1;
	for (int i = 0; i < k; i++) {
		type = op[i] - 1;
		l = left1[i];
		r = right1[i];
		val = height[i] + 1;
		upd (1,0,n-1);
	}
	get(1,0,n-1);
	for (int i = 0;i < n; i++)
		finalHeight[i] = max (A[i] - 1,0);
}   /*
main() {    /*
	freopen("wads.txt","r",stdin);
	freopen("wall.out","w",stdout);
	cin >> n;
	cin >> k;
	for (int i  = 0; i < k; i++) {
		cin >> op[i] >> left1[i] >> right1[i] >> height[i];
	}
	//cout << 
	buildWall();
	for (int i = 0; i < n; i++) cout << finalHeight[i] <<'\n';
	return 0;   
}          */
/* 10 6
1 1 8 4
2 4 9 1 
2 3 6 5
1 0 5 3
1 2 2 5 
2 6 7 0
*/

Compilation message

wall.cpp:90:13: warning: "/*" within comment [-Wcomment]
 main() {    /*

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 94200 KB Output is correct
2 Correct 55 ms 94456 KB Output is correct
3 Correct 56 ms 94328 KB Output is correct
4 Correct 64 ms 94584 KB Output is correct
5 Correct 57 ms 94584 KB Output is correct
6 Correct 58 ms 94584 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 94256 KB Output is correct
2 Correct 255 ms 107820 KB Output is correct
3 Correct 287 ms 101496 KB Output is correct
4 Correct 696 ms 109252 KB Output is correct
5 Correct 399 ms 109688 KB Output is correct
6 Correct 391 ms 109560 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 94200 KB Output is correct
2 Correct 55 ms 94328 KB Output is correct
3 Correct 55 ms 94328 KB Output is correct
4 Correct 60 ms 94584 KB Output is correct
5 Correct 58 ms 94584 KB Output is correct
6 Correct 59 ms 94584 KB Output is correct
7 Correct 53 ms 94204 KB Output is correct
8 Correct 249 ms 107896 KB Output is correct
9 Correct 284 ms 101624 KB Output is correct
10 Correct 696 ms 109176 KB Output is correct
11 Correct 384 ms 109560 KB Output is correct
12 Correct 370 ms 109688 KB Output is correct
13 Correct 52 ms 94200 KB Output is correct
14 Correct 267 ms 108024 KB Output is correct
15 Correct 94 ms 95480 KB Output is correct
16 Correct 792 ms 109512 KB Output is correct
17 Correct 397 ms 109432 KB Output is correct
18 Correct 372 ms 109304 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 94200 KB Output is correct
2 Correct 55 ms 94456 KB Output is correct
3 Correct 54 ms 94328 KB Output is correct
4 Correct 59 ms 94584 KB Output is correct
5 Correct 59 ms 94584 KB Output is correct
6 Correct 57 ms 94624 KB Output is correct
7 Correct 53 ms 94200 KB Output is correct
8 Correct 251 ms 107896 KB Output is correct
9 Correct 285 ms 101452 KB Output is correct
10 Correct 708 ms 109128 KB Output is correct
11 Correct 393 ms 109680 KB Output is correct
12 Correct 361 ms 109688 KB Output is correct
13 Correct 52 ms 94200 KB Output is correct
14 Correct 259 ms 107896 KB Output is correct
15 Correct 95 ms 95480 KB Output is correct
16 Correct 815 ms 109432 KB Output is correct
17 Correct 379 ms 109432 KB Output is correct
18 Correct 388 ms 109288 KB Output is correct
19 Correct 786 ms 133664 KB Output is correct
20 Correct 785 ms 131176 KB Output is correct
21 Correct 820 ms 133772 KB Output is correct
22 Correct 800 ms 131236 KB Output is correct
23 Correct 793 ms 131368 KB Output is correct
24 Correct 780 ms 131320 KB Output is correct
25 Correct 775 ms 131192 KB Output is correct
26 Correct 816 ms 133752 KB Output is correct
27 Correct 798 ms 133624 KB Output is correct
28 Correct 778 ms 131296 KB Output is correct
29 Correct 788 ms 131200 KB Output is correct
30 Correct 781 ms 131192 KB Output is correct