oj.uz

Submission #235985

# Submission time Handle Problem Language Result Execution time Memory
235985 2020-05-30T14:58:05 Z crossing0ver Wall (IOI14_wall) C++17
0 / 100
 265 ms 133624 KB 
#include<bits/stdc++.h>
#include "wall.h"
using namespace std;
const int N = 2E6;
int t[4*N][2],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][0] < lazy[v][0]) t[v*2][0] = 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][0] < lazy[v][0]) t[v*2|1][0] = lazy[v][0];
		}
		if (lazy[v*2][1] < 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]; 
		}
		if (!t[v*2][1] || t[v*2][0] > t[v*2][1]) t[v*2][1] = t[v*2][0];
		if (!t[v*2|1][1] || t[v*2|1][0] > t[v*2|1][1]) t[v*2|1][1] = t[v*2|1][0];
		lazy[v][0] = 0;
	}
	if (lazy[v][1]) {
		if (lazy[v*2][1] < lazy[v][1]) {
			lazy[v*2][1] = lazy[v][1];
			if (t[v*2][1] > lazy[v][1]) t[v*2][1] = lazy[v][1];
		}
		if (lazy[v*2|1][1] < lazy[v][1]) {
			lazy[v*2|1][1]  = lazy[v*2][1];
			if (t[v*2|1][1] > lazy[v][1]) t[v*2|1][1] = lazy[v][1];
		}
			if (lazy[v*2][0] > lazy[v*2][1] ){
				lazy[v*2][0] = lazy[v*2][1];
				t[v*2][0] = min(lazy[v][0],t[v*2][0]);
			}
			if (lazy[v*2|1][0] > lazy[v*2|1][1] ){
				lazy[v*2|1][0] = lazy[v*2|1][1];
				t[v*2|1][0] = min(lazy[v][0],t[v*2|1][0]);
			}
			if (t[v*2][0] > lazy[v*2][1]) t[v*2][0] = lazy[v*2][1];
			if (t[v*2|1][0] > lazy[v*2|1][1]) t[v*2|1][0] = lazy[v*2|1][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 (t[v][0] >= val) return;
			t[v][0] = max (t[v][0],val);
			lazy[v][0] = max (lazy[v][0],val);
			if (lazy[v][1] < val) {
				lazy[v][1] = val;
				t[v][1] = max(t[v][1],val);
			}
		}
		else {
			if (t[v][1] <= val && t[v][1]) return;
			t[v][1] = val;
			if (!lazy[v][1] || lazy[v][1] > val)
				lazy[v][1] = val;
			if (lazy[v][0] > val) {
				lazy[v][0] = val;
				t[v][0] = min(t[v][0],val);
			}
		}
		return;
	}
	push (v,tl,tr);
	int tm = (tl + tr)/2;
	upd (v*2,tl,tm);
	upd (v*2|1,tm+1,tr);
	t[v][0] = min(t[v*2][0],t[v*2|1][0]);
	t[v][1] = max(t[v*2][1],t[v*2|1][1]);
	if (t[v][1] < t[v][0]) t[v][1] = t[v][0];
}
int A[N];
void get (int v,int tl,int tr) {
	if (tl == tr) A[tl] = min(t[v][1],t[v][0]);
	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 left[], int right[],int height[], int finalHeight[]) {
	for (int i = 0; i < 4*N; i++) lazy[i][1] = t[i][1] = 1e9;
	for (int i = 0; i < k; i++) {
		type = op[i] - 1;
		l = left[i];
		r = right[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);
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 125560 KB Output is correct
2 Correct 67 ms 125688 KB Output is correct
3 Incorrect 73 ms 125560 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 125564 KB Output is correct
2 Correct 233 ms 133624 KB Output is correct
3 Incorrect 265 ms 129144 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 125560 KB Output is correct
2 Correct 69 ms 125688 KB Output is correct
3 Incorrect 74 ms 125560 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 125560 KB Output is correct
2 Correct 68 ms 125688 KB Output is correct
3 Incorrect 70 ms 125560 KB Output isn't correct
4 Halted 0 ms 0 KB -