oj.uz

Submission #132073

# Submission time Handle Problem Language Result Execution time Memory
132073 2019-07-18T09:28:57 Z Sorting Wall (IOI14_wall) C++14
0 / 100
 808 ms 81048 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 2e6 + 7;
const int inf = 1e9;

struct node{
	int mn, mx;

	node(){
		mx = -inf;
		mn  = inf;
	};
	node(int _mn, int _mx){
		mn = _mn;
		mx = _mx;
	}

	friend void unite(node &prev, node after){
		prev.mn = min(prev.mn, after.mn);
		prev.mx = max(prev.mx, after.mx);

		if(prev.mx > prev.mn){
			if(after.mx == prev.mx){
				prev.mn = prev.mx;
			}
			else{
				prev.mx = prev.mn;
			}
		}
	}
};

node st[4 * N];

void update(int idx, int l, int r, int sl, int sr, node val){
	if(l != r){
		unite(st[2 * idx], st[idx]);
		unite(st[2 * idx + 1], st[idx]);
		st[idx] = node();
	}

	if(l > sr || r < sl){
		return;
	}
	if(sl <= l && r <= sr){
		unite(st[idx], val);

		return;
	}

	int mid = (l + r) / 2;

	update(2 * idx, l, mid, sl, sr, val);
	update(2 * idx + 1, mid + 1, r, sl, sr, val);
}

int query(int idx, int l, int r, int s){
	if(l != r){
		unite(st[2 * idx], st[idx]);
		unite(st[2 * idx + 1], st[idx]);
		st[idx] = node();
	}

	if(l > s || r < s){
		return node().mx;
	}
	if(l == r && l == s){
		return st[idx].mx;
	}

	int mid = (l + r) >> 1;

	int lvalue = query(2 * idx, l, mid, s);
	int rvalue = query(2 * idx + 1, mid + 1, r, s);

	return max(lvalue, rvalue);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	for(int i = 0; i < k; i++){
		node t;

		if(op[i] == 1){
			t = node(inf, height[i]);
		}
		else{
			t = node(height[i], -inf);
		}

		update(1, 0, n - 1, left[i], right[i], t);
	}

	for(int i = 0; i < n; i++){
		finalHeight[i] = query(1, 0, n - 1, i); 
	}
}

/*int n, k, op2[N], left2[N], right2[N], height2[N], finalHeight2[N];

int main(){
	cin >> n >> k;

	for(int i = 0; i < k; i++){
		cin >> op2[i] >> left2[i] >> right2[i] >> height2[i];
	}

	buildWall(n, k, op2, left2, right2, height2, finalHeight2);

	for(int i = 0; i < n; i++){
		cout << finalHeight2[i] << " ";
	}
	cout << "\n";
	
	return 0;
}*/

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 62940 KB Output is correct
2 Correct 67 ms 63284 KB Output is correct
3 Correct 56 ms 62968 KB Output is correct
4 Incorrect 68 ms 63252 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 62968 KB Output is correct
2 Correct 224 ms 76708 KB Output is correct
3 Correct 312 ms 70136 KB Output is correct
4 Incorrect 808 ms 81048 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 62940 KB Output is correct
2 Correct 57 ms 63096 KB Output is correct
3 Correct 57 ms 62940 KB Output is correct
4 Incorrect 66 ms 63276 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 62968 KB Output is correct
2 Correct 57 ms 63224 KB Output is correct
3 Correct 57 ms 62968 KB Output is correct
4 Incorrect 66 ms 63352 KB Output isn't correct
5 Halted 0 ms 0 KB -