Submission #1327652

#	Time	Username	Problem	Language	Result	Execution time	Memory
1327652		gs12117	Pyramid Base (IOI08_pyramid_base)	C++17	65 / 100	576 ms	67764 KiB

pyramid_base

#include<cstdio>
#include<algorithm>
int m, n, b, p;
int pyr[401000][5];
struct st {
	int x, yl, yr;
	int val;
	bool operator<(const st& r)const {
		return x < r.x;
	}
};
st sl[801000];
const int itsz = 1 << 20;
int logitsz = 20;
struct itnode {
	int cover;
	int len;
	int lemp, remp, iemp;
	bool havecover;
	itnode operator+(const itnode& r)const {
		itnode res;
		res.cover = 0;
		res.len = len + r.len;
		res.lemp = lemp;
		res.remp = r.remp;
		if (!havecover) {
			res.lemp = len + r.lemp;
		}
		if (!r.havecover) {
			res.remp = r.len + remp;
		}
		res.havecover = (havecover || r.havecover);
		res.iemp = remp + r.lemp;
		if (res.iemp < iemp)res.iemp = iemp;
		if (res.iemp < r.iemp)res.iemp = r.iemp;
		return res;
	}
};
itnode it[2 * itsz];
itnode basenode() {
	itnode res;
	res.len = 1;
	res.cover = 0;
	res.havecover = false;
	res.lemp = res.len;
	res.remp = res.len;
	res.iemp = res.len;
	return res;
}
itnode nonode() {
	itnode res;
	res.len = 0;
	res.cover = 0;
	res.havecover = false;
	res.lemp = res.len;
	res.remp = res.len;
	res.iemp = res.len;
	return res;
}
void addcover(int x, int v) {
	it[x].cover += v;
	if (it[x].cover > 0) {
		it[x].lemp = 0;
		it[x].remp = 0;
		it[x].iemp = 0;
		it[x].havecover = true;
	}
	else {
		if (x >= itsz) {
			it[x].havecover = false;
			it[x].lemp = it[x].len;
			it[x].remp = it[x].len;
			it[x].iemp = it[x].len;
		}
		else {
			it[x] = it[x * 2] + it[x * 2 + 1];
		}
	}
}
void upcover(int x) {
	if (x >= itsz)return;
	if (it[x].cover <= 0) {
		it[x] = it[x * 2] + it[x * 2 + 1];
	}
}
void itinit(int len) {
	for (int i = 1; i <= len; i++) {
		it[itsz + i] = basenode();
	}
	int s = itsz + 1;
	int e = itsz + len;
	s /= 2;
	e /= 2;
	while (s > 0) {
		for (int i = s; i <= e; i++) {
			it[i] = it[i * 2] + it[i * 2 + 1];
		}
		s /= 2;
		e /= 2;
	}
}
void itpush(int start, int end, int val) {
	start += itsz;
	end += itsz;
	int ps = start;
	int pe = end;
	while (start <= end) {
		if (start % 2 == 1) {
			addcover(start, val);
			start++;
		}
		if (end % 2 == 0) {
			addcover(end, val);
			end--;
		}
		start /= 2;
		end /= 2;
	}
	for (int i = 1; i <= logitsz; i++) {
		upcover(ps >> i);
		if ((pe >> i) != (ps >> i))upcover(pe >> i);
	}
}
int itcalc() {
	return it[1].iemp;
}
int main() {
	scanf("%d%d%d%d", &m, &n, &b, &p);
	for (int i = 0; i < p; i++) {
		scanf("%d%d%d%d%d", &pyr[i][0], &pyr[i][1], &pyr[i][2], &pyr[i][3], &pyr[i][4]);
		sl[i * 2].x = pyr[i][0];
		sl[i * 2].yl = pyr[i][1];
		sl[i * 2].yr = pyr[i][3];
		sl[i * 2].val = 1;
		sl[i * 2 + 1].x = pyr[i][2];
		sl[i * 2 + 1].yl = pyr[i][1];
		sl[i * 2 + 1].yr = pyr[i][3];
		sl[i * 2 + 1].val = -1;
	}
	std::sort(sl, sl + 2 * p);
	sl[2 * p].x = 2 * (m + n) + 1000;
	int xl = 0;
	int xr = 0;
	int pl = 0;
	int pr = 0;
	itinit(n);
	int ans = 0;
	while (xr <= m) {
		int xd = xr - xl;
		int yd = itcalc();
		if (yd < xd) {
			if (ans < yd)ans = yd;
			xl++;
			while (sl[pl].x <= xl) {
				if (sl[pl].val < 0)itpush(sl[pl].yl, sl[pl].yr, sl[pl].val);
				pl++;
			}
		}
		else {
			if (ans < xd)ans = xd;
			xr++;
			while (sl[pr].x <= xr) {
				if (sl[pr].val > 0)itpush(sl[pr].yl, sl[pr].yr, sl[pr].val);
				pr++;
			}
		}
	}
	printf("%d\n", ans);
	return 0;
}

Compilation message (stderr)

pyramid_base.cpp: In function 'int main()':
pyramid_base.cpp:128:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  128 |         scanf("%d%d%d%d", &m, &n, &b, &p);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
pyramid_base.cpp:130:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  130 |                 scanf("%d%d%d%d%d", &pyr[i][0], &pyr[i][1], &pyr[i][2], &pyr[i][3], &pyr[i][4]);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 5 / 5
• Subtask 8: 0 / 7
• Subtask 9: 0 / 7
• Subtask 10: 0 / 7
• Subtask 11: 0 / 7
• Subtask 12: 0 / 7
• Subtask 13: 10 / 10
• Subtask 14: 10 / 10
• Subtask 15: 10 / 10