Submission #118806

#	Time	Username	Problem	Language	Result	Execution time	Memory
118806		eriksuenderhauf	Pyramid Base (IOI08_pyramid_base)	C++11	100 / 100	2055 ms	85868 KiB

pyramid_base

//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#define mem(a,v) memset((a), (v), sizeof (a))
#define enl printf("\n")
#define case(t) printf("Case #%d: ", (t))
#define ni(n) scanf("%d", &(n))
#define nl(n) scanf("%I64d", &(n))
#define nai(a, n) for (int i = 0; i < (n); i++) ni(a[i])
#define nal(a, n) for (int i = 0; i < (n); i++) nl(a[i])
#define pri(n) printf("%d\n", (n))
#define prl(n) printf("%I64d\n", (n))
#define pii pair<int, int>
#define pil pair<int, long long>
#define pll pair<long long, long long>
#define vii vector<pii>
#define vil vector<pil>
#define vll vector<pll>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef cc_hash_table<int,int,hash<int>> ht;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> oset;
const double pi = acos(-1);
const int MOD = 1e9 + 7;
const ll INF = 1e16 + 7;
const int MAXN = 1e6 + 5;
const double eps = 1e-9;

struct rec {
	pii lo, hi;
	ll c;
} a[MAXN];

struct sweep {
	int t; // 1->qry, 0->insert, 2->erase
	int pos; // x
	pii loc; // y - range
	ll cost;

	bool operator<(const sweep rhs) const {
		if (pos == rhs.pos)
			return t < rhs.t;
		return pos < rhs.pos;
	}
};

ll seg[MAXN*3], lazy[MAXN*3];

void prop(int l, int r, int k) {
	if (lazy[k] == 0) return;
	if (l != r) {
		lazy[k*2] += lazy[k];
		lazy[k*2+1] += lazy[k];
	}
	seg[k] += lazy[k];
	lazy[k] = 0;
}

void upd(int l, int r, int k, int a, int b, ll v) {
	prop(l, r, k);
	if (r < a || b < l) return;
	if (a <= l && r <= b) {
		lazy[k] += v;
		prop(l, r, k);
		return;
	}
	int m = (l+r) / 2;
	upd(l, m, k*2, a, b, v);
	upd(m+1, r, k*2+1, a, b, v);
	seg[k] = min(seg[k*2], seg[k*2+1]);
}

ll qry(int l, int r, int k, int a, int b) {
	prop(l, r, k);
	if (b < l || r < a) return INF;
	if (a <= l && r <= b) return seg[k];
	int m = (l+r) / 2;
	return min(qry(l,m,k*2,a,b), qry(m+1,r,k*2+1,a,b));
}

int m, n, p; ll b;
int vis[MAXN];

ll f(int w) {
	mem(vis, 0);
	vector<sweep> arr;
	for (int i = 0; i < p; i++) {
		arr.pb({0, a[i].lo.fi, mp(max(1,a[i].lo.se - w+1), a[i].hi.se), a[i].c});
		arr.pb({2, min(m, a[i].hi.fi + w-1), mp(max(1,a[i].lo.se - w+1), a[i].hi.se), -a[i].c});
		arr.pb({1, max(w, a[i].lo.fi - 1), mp(0, 0), 0});
	}
	arr.pb({1, m, mp(0, 0)});
	sort(arr.begin(), arr.end());
	ll ret = INF;
	for (int i = 0; i < arr.size(); i++) {
		sweep cur = arr[i];
		if (cur.t == 1 && vis[cur.pos])
			continue;
		if (cur.t == 0)
			upd(1, n, 1, cur.loc.fi, cur.loc.se, cur.cost);
		else if (cur.t == 1) {
			vis[cur.pos] = 1;
			ret = min(ret, qry(1, n, 1, 1, n-w+1));
			if (ret <= b) {
				mem(seg, 0);
				mem(lazy, 0);
				return ret;
			}
		} else
			upd(1, n, 1, cur.loc.fi, cur.loc.se, cur.cost);
	}
	return ret;
}

struct sweep2 {
	int pos, x, y;

	bool operator<(const sweep2 rhs) const {
		return pos < rhs.pos;
	}
};

struct node {
	int ls, rs, mx, len;
} seg2[MAXN*4];
int lz[MAXN*4];

void merge(node& c, node &a, node &b) {
	c.len = a.len + b.len;
	c.ls = a.ls;
	if (a.len == a.mx)
		c.ls += b.ls;
	c.rs = b.rs;
	if (b.len == b.mx)
		c.rs += a.rs;
	c.mx = max(max(a.mx, b.mx), max(max(c.ls, c.rs), a.rs + b.ls));
}

void build(int l, int r, int k) {
	if (l == r) {
		seg2[k] = {1, 1, 1, 1};
		return;
	}
	int m = (l+r) / 2;
	build(l, m, k*2);
	build(m+1, r, k*2+1);
	merge(seg2[k], seg2[k*2], seg2[k*2+1]);
}

void upd2(int l, int r, int k, int a, int b, int v) {
	if (r < a || b < l) return;
	if (a <= l && r <= b) {
		lz[k] += v;
		if (lz[k])
			seg2[k] = {0, 0, 0, seg2[k].len};
		else if (l == r)
			seg2[k] = {1, 1, 1, 1};
		else
			merge(seg2[k], seg2[k*2], seg2[k*2+1]);
		return;
	}
	int m = (l+r) / 2;
	upd2(l, m, k*2, a, b, v);
	upd2(m+1, r, k*2+1, a, b, v);
	if (lz[k])
		seg2[k] = {0, 0, 0, seg2[k].len};
	else
		merge(seg2[k], seg2[k*2], seg2[k*2+1]);
}

int solve() {
	build(1, n, 1);
	vector<sweep2> st, en;
	en.pb({0, 1, 0});
	for (int i = 0; i < p; i++) {
		st.pb({a[i].lo.fi, a[i].lo.se, a[i].hi.se});
		en.pb({a[i].hi.fi + 1, a[i].lo.se, a[i].hi.se});
	}
	sort(st.begin(), st.end());
	sort(en.begin(), en.end());
	int ans = 0, lo = 1, hi = st[0].pos, r = 0;
	for (int i = 0; i < en.size();) {
		ans = max(ans, min(hi - lo, seg2[1].mx));
		while (r < st.size() && seg2[1].mx > hi - lo) {
			int tmp = r;
			while (tmp < st.size() && st[tmp].pos == st[r].pos) {
				upd2(1, n, 1, st[tmp].x, st[tmp].y, 1);
				tmp++;
			}
			r = tmp;
			if (r == st.size())
				hi = m+1;
			else
				hi = st[r].pos;
			ans = max(ans, min(hi - lo, seg2[1].mx));
		}
		int tmp = i;
		while (tmp < en.size() && en[tmp].pos == en[i].pos) tmp++;
		while (tmp < en.size() && r < st.size() && st[r].pos <= en[tmp].pos) {
			upd2(1, n, 1, st[r].x, st[r].y, 1);
			r++;
		}
		if (r == st.size())
			hi = m+1;
		else
			hi = st[r].pos;
		lo = en[i].pos;
		while (i < tmp) {
			upd2(1, n, 1, en[i].x, en[i].y, -1);
			i++;
		}
	}
	pri(ans);
	return 0;
}

int main() {
	scanf("%d %d %lld %d", &m, &n, &b, &p);
	for (int i = 0; i < p; i++)
		scanf("%d %d %d %d %lld", &a[i].lo.fi, &a[i].lo.se, &a[i].hi.fi, &a[i].hi.se, &a[i].c);
	if (b == 0) return solve();
	int lo = 1, hi = min(m, n), ans = 0;
	while (lo <= hi) {
		int mi = (lo + hi) / 2;
		if (f(mi) <= b)
			lo = mi + 1, ans = mi;
		else
			hi = mi - 1;
	}
	pri(ans);
    return 0;
}

Compilation message (stderr)

pyramid_base.cpp: In function 'll f(int)':
pyramid_base.cpp:104:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < arr.size(); i++) {
                  ~~^~~~~~~~~~~~
pyramid_base.cpp: In function 'int solve()':
pyramid_base.cpp:191:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < en.size();) {
                  ~~^~~~~~~~~~~
pyramid_base.cpp:193:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (r < st.size() && seg2[1].mx > hi - lo) {
          ~~^~~~~~~~~~~
pyramid_base.cpp:195:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while (tmp < st.size() && st[tmp].pos == st[r].pos) {
           ~~~~^~~~~~~~~~~
pyramid_base.cpp:200:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (r == st.size())
        ~~^~~~~~~~~~~~
pyramid_base.cpp:207:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (tmp < en.size() && en[tmp].pos == en[i].pos) tmp++;
          ~~~~^~~~~~~~~~~
pyramid_base.cpp:208:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (tmp < en.size() && r < st.size() && st[r].pos <= en[tmp].pos) {
          ~~~~^~~~~~~~~~~
pyramid_base.cpp:208:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (tmp < en.size() && r < st.size() && st[r].pos <= en[tmp].pos) {
                             ~~^~~~~~~~~~~
pyramid_base.cpp:212:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (r == st.size())
       ~~^~~~~~~~~~~~
pyramid_base.cpp: In function 'int main()':
pyramid_base.cpp:227:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %lld %d", &m, &n, &b, &p);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
pyramid_base.cpp:229:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d %d %lld", &a[i].lo.fi, &a[i].lo.se, &a[i].hi.fi, &a[i].hi.se, &a[i].c);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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: 7 / 7
• Subtask 9: 7 / 7
• Subtask 10: 7 / 7
• Subtask 11: 7 / 7
• Subtask 12: 7 / 7
• Subtask 13: 10 / 10
• Subtask 14: 10 / 10
• Subtask 15: 10 / 10