oj.uz

Submission #77126

# Submission time Handle Problem Language Result Execution time Memory
77126 2018-09-22T14:38:17 Z FiloSanza Wall (IOI14_wall) C++14
61 / 100
 1243 ms 263168 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
const int INF = 2e9;

struct Segment{
	inline int left(int i){return (i*2)+1;}
	inline int right(int i){return (i+1)*2;}

	vector<int> v;
	vector<int> maxi;
	vector<int> mini;
	int S;

	Segment(int N){
		S = (1<<(int)ceil(log2(N)+1))-1;
		v.resize(S, 0);
		mini.resize(S, INF);
		maxi.resize(S, -INF);
	}

	void check(int pos){
		if(mini[pos] == -INF) return; //mai aggiornato
		v[pos] = max(mini[pos], v[pos]);
		v[pos] = min(maxi[pos], v[pos]);
		if(pos < S/2){
			if(maxi[left(pos)] < mini[pos]) mini[left(pos)] = maxi[left(pos)] = mini[pos];
			if(maxi[pos] < mini[left(pos)]) mini[left(pos)] = maxi[left(pos)] = maxi[pos];
			maxi[left(pos)] = min(maxi[pos], maxi[left(pos)]);
			mini[left(pos)] = max(mini[pos], mini[left(pos)]);
			if(maxi[right(pos)] < mini[pos]) mini[right(pos)] = maxi[right(pos)] = mini[pos];
			if(maxi[pos] < mini[right(pos)]) mini[right(pos)] = maxi[right(pos)] = maxi[pos];
			maxi[right(pos)] = min(maxi[pos], maxi[right(pos)]);
			mini[right(pos)] = max(mini[pos], mini[right(pos)]);
		}

		mini[pos] = -INF;
		maxi[pos] = INF;
	}

	void update(int pos, int a, int b, int l, int r, int mm, int MM){
		if(a > r || b < l)
			return;
		check(pos);
		if(a >= l && b <= r){
			if(maxi[pos] < mm) maxi[pos] = mini[pos] = mm;
			if(mm < mini[pos]) maxi[pos] = mini[pos] = MM;
			maxi[pos] = min(maxi[pos], MM);
			mini[pos] = max(mini[pos], mm);
			check(pos);
			return;
		}
		int mid = (a+b)/2;
		update(left(pos), a, mid, l, r, mm, MM);
		update(right(pos), mid+1, b, l, r, mm, MM);
	}

	void updateAll(){
		for(int i=0; i<S; i++)
			check(i);
	}

	int getAt(int i){
		return v[S/2+i];
	}
};	

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	Segment st(n);
	for(int i=0; i<k; i++){
		if(op[i] == 1)
			st.update(0, 0, st.S/2, left[i], right[i], height[i], INF);
		else
			st.update(0, 0, st.S/2, left[i], right[i], 0, height[i]);
	}
	
	st.updateAll();

	for(int i=0; i<n; i++)
		finalHeight[i] = st.getAt(i) == -INF ? 0 : st.getAt(i);
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 4 ms 504 KB Output is correct
3 Correct 4 ms 544 KB Output is correct
4 Correct 13 ms 1252 KB Output is correct
5 Correct 8 ms 1464 KB Output is correct
6 Correct 8 ms 1548 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1548 KB Output is correct
2 Correct 194 ms 14696 KB Output is correct
3 Correct 347 ms 14968 KB Output is correct
4 Correct 937 ms 31696 KB Output is correct
5 Correct 354 ms 41812 KB Output is correct
6 Correct 363 ms 50520 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 50520 KB Output is correct
2 Correct 4 ms 50520 KB Output is correct
3 Correct 4 ms 50520 KB Output is correct
4 Correct 16 ms 50520 KB Output is correct
5 Correct 8 ms 50520 KB Output is correct
6 Correct 8 ms 50520 KB Output is correct
7 Correct 2 ms 50520 KB Output is correct
8 Correct 194 ms 53088 KB Output is correct
9 Correct 301 ms 53224 KB Output is correct
10 Correct 880 ms 70028 KB Output is correct
11 Correct 352 ms 80268 KB Output is correct
12 Correct 352 ms 88900 KB Output is correct
13 Correct 2 ms 88900 KB Output is correct
14 Correct 199 ms 91108 KB Output is correct
15 Correct 67 ms 91108 KB Output is correct
16 Correct 1243 ms 104956 KB Output is correct
17 Correct 339 ms 114044 KB Output is correct
18 Correct 382 ms 123204 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 123204 KB Output is correct
2 Correct 4 ms 123204 KB Output is correct
3 Correct 4 ms 123204 KB Output is correct
4 Correct 12 ms 123204 KB Output is correct
5 Correct 9 ms 123204 KB Output is correct
6 Correct 8 ms 123204 KB Output is correct
7 Correct 2 ms 123204 KB Output is correct
8 Correct 201 ms 125992 KB Output is correct
9 Correct 296 ms 125992 KB Output is correct
10 Correct 874 ms 142888 KB Output is correct
11 Correct 391 ms 152616 KB Output is correct
12 Correct 333 ms 161248 KB Output is correct
13 Correct 2 ms 161248 KB Output is correct
14 Correct 267 ms 163412 KB Output is correct
15 Correct 69 ms 163412 KB Output is correct
16 Correct 1231 ms 177164 KB Output is correct
17 Correct 361 ms 186132 KB Output is correct
18 Correct 336 ms 195236 KB Output is correct
19 Correct 1006 ms 258036 KB Output is correct
20 Runtime error 1006 ms 263168 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
21 Halted 0 ms 0 KB -