oj.uz

Submission #408115

# Submission time Handle Problem Language Result Execution time Memory
408115 2021-05-19T05:59:54 Z mshandilya Wall (IOI14_wall) C++14
0 / 100
 244 ms 13900 KB 
#include <bits/stdc++.h>
#include "wall.h"

using namespace std;

void add(std::vector<int>& ST, std::vector<int>& lazy, int update, int rbeg, int rend, int beg, int end, int node) {
	if(rbeg>rend)
		return;
	if(lazy[node-1]!=-1) {
		ST[node-1] = lazy[node-1];
		lazy[2*node-1] = lazy[node-1];
		lazy[2*node] = lazy[node-1]; 
		lazy[node-1] = -1;
	}
	if(rbeg==beg and rend==end) {
		ST[node-1] = max(update, ST[node-1]);
		if(lazy[2*node-1]==-1)
			lazy[2*node-1] = max(update, ST[2*node-1]);
		else
			lazy[2*node-1] = max(update, lazy[2*node-1]);
		if(lazy[2*node]==-1)
			lazy[2*node] = max(update, ST[2*node]);
		else
			lazy[2*node] = max(update, lazy[2*node]);
		return;
	}
	int mid = (beg+end)/2;
	add(ST, lazy, update, rbeg, min(mid, rend), beg, mid, 2*node);
	add(ST, lazy, update, max(rbeg, mid+1), rend, mid+1, end, 2*node+1);
	return;
}

void remov(std::vector<int>& ST, std::vector<int>& lazy, int update, int rbeg, int rend, int beg, int end, int node) {
	if(rbeg>rend)
		return;
	if(lazy[node-1]!=-1) {
		ST[node-1] = lazy[node-1];
		lazy[2*node-1] = lazy[node-1];
		lazy[2*node] = lazy[node-1];
		lazy[node-1] = -1;
	}
	if(rbeg==beg and rend==end) {
		ST[node-1] = min(update, ST[node-1]);
		if(lazy[2*node-1]==-1)
			lazy[2*node-1] = min(update, ST[2*node-1]);
		else
			lazy[2*node-1] = min(update, lazy[2*node-1]);
		if(lazy[2*node]==-1)
			lazy[2*node] = min(update, ST[2*node]);
		else
			lazy[2*node] = min(update, lazy[2*node]);
		return;
	}
	int mid = (beg+end)/2;
	remov(ST, lazy, update, rbeg, min(mid, rend), beg, mid, 2*node);
	remov(ST, lazy, update, max(rbeg, mid+1), rend, mid+1, end, 2*node+1);
	return;
}

int retrieve(std::vector<int>& ST, std::vector<int>& lazy, int find, int beg, int end, int node) {
	if(lazy[node-1]!=-1) {
		ST[node-1] = lazy[node-1];
		lazy[2*node-1] = lazy[node-1];
		lazy[2*node] = lazy[node-1];
		lazy[node-1] = -1;
	}
	if(beg==end)
		return ST[node-1];
	int mid = (beg+end)/2;
	if(find<=mid)
		return retrieve(ST, lazy, find, beg, mid, 2*node);
	else
		return retrieve(ST, lazy, find, mid+1, end, 2*node+1);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	int st_size = 1;
	while(st_size<n)
		st_size<<=1;
	std::vector<int> ST(2*st_size-1, 0), lazy(2*st_size-1, -1);
	for (int i = 0; i<k; ++i) {
		if(op[i]==1)
			add(ST, lazy, height[i], left[i], right[i], 0, st_size-1, 1);
		else
			remov(ST, lazy, height[i], left[i], right[i], 0, st_size-1, 1);	
	}
	for(int i = 0; i<n; i++)
		finalHeight[i] = retrieve(ST, lazy, i, 0, st_size-1, 1);
	return;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 332 KB Output is correct
3 Runtime error 4 ms 460 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 207 ms 13900 KB Output is correct
3 Runtime error 244 ms 11360 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 4 ms 432 KB Output is correct
3 Runtime error 4 ms 460 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 3 ms 440 KB Output is correct
3 Runtime error 4 ms 508 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -