Submission #773252

#	Time	Username	Problem	Language	Result	Execution time	Memory
773252		therealpain	Wall (IOI14_wall)	C++17	0 / 100	37 ms	94216 KiB

wall

#include <bits/stdc++.h> 
#define fi first 
#define se second
#define mp make_pair
#define getbit(x, i) (((x) >> (i)) & 1)
#define all(x) x.begin(), x.end()
#define TASK ""
 
using namespace std;
 
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
	if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
	if (a < b) {a = b; return true;} return false;
}
 
const long long inf = 1e18;
const int mod = 1e9 + 7;
const int N = 2e6 + 7;

int ans[N];
int n, k;

struct IntervalTree {
	int n;
	int st[4 * N];
	pair <int, int> lazy[4 * N];

	IntervalTree(int n) {
		this -> n = n;
		for (int i = 1; i <= 4 * n; ++i) {
			st[i] = 0;
			lazy[i] = mp(-1e9, 1e9);
		}
	}

	void fix(int id, int l, int r, int type) {
		if (type == 1) 
            maxi(st[id], lazy[id].fi);
		else 
            mini(st[id], lazy[id].se);
        if (l < r) {
            if (type == 1) {
                maxi(lazy[id << 1].fi, lazy[id].fi);
                maxi(lazy[id << 1].se, lazy[id].fi);
                maxi(lazy[id << 1 | 1].fi, lazy[id].fi);
                maxi(lazy[id << 1 | 1].se, lazy[id].fi);
            } else {
                mini(lazy[id << 1].fi, lazy[id].se);
                mini(lazy[id << 1].se, lazy[id].se);
                mini(lazy[id << 1 | 1].fi, lazy[id].se);
                mini(lazy[id << 1 | 1].se, lazy[id].se);
            }
        }
        if (type == 1) {
        	lazy[id].fi = -1e9;
        } else 
        	lazy[id].se = 1e9;
	}

	void update(int u, int v, int h, int type, int id = 1, int l = 1, int r = -1) {
		if (r < 0) r = n;
		fix(id, l, r, 0);
		fix(id, l, r, 1);
		if (l > v || r < u) return;
		if (u <= l && r <= v) {
			if (type == 1) {
				maxi(lazy[id].fi, h);
				maxi(lazy[id].se, h);
			} else {
				mini(lazy[id].fi, h);
				mini(lazy[id].se, h);
			}
			fix(id, l, r, type);
			return;
		}

		int mid = l + r >> 1;
		update(u, v, h, type, id << 1, l, mid);
		update(u, v, h, type, id << 1 | 1, mid + 1, r);
	}

	void get(int id = 1, int l = 1, int r = -1) {
		if (r < 0) r = n;
		fix(id, l, r, 0);
		fix(id, l, r, 1);
		if (l == r) {
			ans[l] = st[id];
			return;
		}

		int mid = l + r >> 1;
		get(id << 1, l, mid);
		get(id << 1 | 1, mid + 1, r);
	}
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
	IntervalTree IT(n);
	for (int i = 1; i <= k; ++i) {
		IT.update(left[i] + 1, right[i] + 1, height[i], op[i]);
	}
	IT.get();
	for (int i = 1; i <= n; ++i) {
		finalHeight[i - 1] = ans[i];
	}
}

Compilation message (stderr)

wall.cpp: In member function 'void IntervalTree::update(int, int, int, int, int, int, int)':
wall.cpp:79:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   79 |   int mid = l + r >> 1;
      |             ~~^~~
wall.cpp: In member function 'void IntervalTree::get(int, int, int)':
wall.cpp:93:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   93 |   int mid = l + r >> 1;
      |             ~~^~~

• Subtask 1: 0 / 8
• Subtask 2: 0 / 24
• Subtask 3: 0 / 29
• Subtask 4: 0 / 39