oj.uz

Submission #531496

# Submission time Handle Problem Language Result Execution time Memory
531496 2022-02-28T22:52:16 Z jesus_coconut Wall (IOI14_wall) C++17
24 / 100
 339 ms 107988 KB 
#include <bits/stdc++.h>
#include "wall.h"
#define F first
#define S second

using namespace std;

using pii = pair<int, int>;
int const inf = (1 << 28);
int const N = (1 << 21);


struct Item {
  int mx = inf, mx2 = inf;
  int mn = -inf, mn2 = -inf;
};

struct SegTree {
  Item values[2 * N];
  pii lazy[2 * N];
  pii const NO = {inf, -inf};

  Item merge(Item const &a, Item const &b) {
	Item ret;
	ret.mx = max(a.mx, b.mx);
	if (a.mx == b.mx) ret.mx2 = max(a.mx2, b.mx2);
	else {
	  if (a.mx < b.mx) ret.mx2 = max(a.mx, b.mx2);
	  else ret.mx2 = max(a.mx2, b.mx);
	}
	ret.mn = min(a.mn, b.mn);
	if (a.mn == b.mn) ret.mn2 = min(a.mn2, b.mn2);
	else {
	  if (a.mn > b.mn) ret.mn2 = min(a.mn, b.mn2);
	  else ret.mn2 = min(a.mn2, b.mn);
	}
	return ret;
  }

  Item updSing(Item a, pii const &b) {
	if (a.mx == a.mn) {
	  if (b.F < a.mx) {
		a.mx = a.mn = b.F;
	  } else if (b.S > a.mn) {
		a.mx = a.mn = b.S;
	  }
	  return a;
	}
	a.mx = min(a.mx, b.F);
	a.mn = max(a.mn, b.S);
	return a;
  }

  pii updSing(pii const &a, pii const &b) {
	pii ret;
	ret.F = min(a.F, b.F);
	ret.S = max(a.S, b.S);
	if (ret.F < ret.S) {
	  ret.F = ret.S = (ret.F == b.F ? b.F : b.S);
	}
	return ret;
  }

  void upd(int l, int r, pii ud, int ver, int lx, int rx) {
	propagate(ver, lx, rx);
	if (rx <= l || r <= lx || (ud.F >= values[ver].mx && ud.S <= values[ver].mn)) return;
	if (l <= lx && rx <= r && (ud.F > values[ver].mx2 || ud.S < values[ver].mn2)) {
	  values[ver] = updSing(values[ver], ud);
	  lazy[ver] = updSing(lazy[ver], ud);
	  return;
	}
	int M = (lx + rx) / 2;
	upd(l, r, ud, ver * 2 + 1, lx, M);
	upd(l, r, ud, ver * 2 + 2, M, rx);
	values[ver] = merge(values[2 * ver + 1], values[2 * ver + 2]);
  }

  void propagate(int ver, int lx, int rx) {
	if (rx - lx == 1 || lazy[ver] == NO) return;
	for (int i : {1, 2}) {
	  values[2 * ver + i] = updSing(values[2 * ver + i], lazy[ver]);
	  lazy[2 * ver + i] = updSing(lazy[2 * ver + i], lazy[ver]);
	}
	lazy[ver] = NO;
  }

  void upd(int l, int r, pii ud) { upd(l, r, ud, 0, 0, N); }

  void propAll(int ver = 0, int lx = 0, int rx = N) {
	propagate(ver, lx, rx);
	if (rx - lx > 1) {
	  int m = (lx + rx) / 2;
	  propAll(2 * ver + 1, lx, m);
	  propAll(2 * ver + 2, m, rx);
	}
  }

  SegTree() {
	fill(values, values + 2 * N, Item{0, -inf, 0, inf});
	fill(lazy, lazy + 2 * N, NO);
  }

};


void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  SegTree st;
  for (int i = 0; i < k; ++i) {
	pii ud{inf, -inf};
	if (op[i] == 1) ud.S = height[i];
	else ud.F = height[i];
	st.upd(left[i], right[i] + 1, ud);
  }
  st.propAll();
  for (int i = 0; i < n; ++i) {
	finalHeight[i] = st.values[N - 1 + i].mx;
  }
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 98768 KB Output is correct
2 Correct 84 ms 98840 KB Output is correct
3 Incorrect 82 ms 98788 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 98756 KB Output is correct
2 Correct 339 ms 106620 KB Output is correct
3 Correct 163 ms 102096 KB Output is correct
4 Correct 253 ms 107444 KB Output is correct
5 Correct 270 ms 107988 KB Output is correct
6 Correct 313 ms 107956 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 98696 KB Output is correct
2 Correct 80 ms 98736 KB Output is correct
3 Incorrect 82 ms 98708 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 98756 KB Output is correct
2 Correct 85 ms 98804 KB Output is correct
3 Incorrect 79 ms 98788 KB Output isn't correct
4 Halted 0 ms 0 KB -