oj.uz

Submission #132065

# Submission time Handle Problem Language Result Execution time Memory
132065 2019-07-18T09:13:41 Z Sorting Wall (IOI14_wall) C++14
0 / 100
 59 ms 63144 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(height[i], inf);
		}
		else{
			t = node(-inf, height[i]);
		}

		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); 
	}
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 55 ms 63096 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 59 ms 63096 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 54 ms 63096 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 54 ms 63144 KB Output isn't correct
2 Halted 0 ms 0 KB -