oj.uz

Submission #118806

# Submission time Handle Problem Language Result Execution time Memory
118806 2019-06-19T20:15:50 Z eriksuenderhauf Pyramid Base (IOI08_pyramid_base) C++11
100 / 100
 2055 ms 85868 KB 
//#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 23808 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 23808 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 23808 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 24576 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 28920 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 61264 KB Output is correct
2 Correct 59 ms 62184 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 59388 KB Output is correct
2 Correct 56 ms 61432 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 75532 KB Output is correct
2 Correct 191 ms 75496 KB Output is correct
3 Correct 146 ms 75464 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 547 ms 77460 KB Output is correct
2 Correct 687 ms 77480 KB Output is correct
3 Correct 557 ms 77428 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 874 ms 77744 KB Output is correct
2 Correct 195 ms 77672 KB Output is correct
3 Correct 384 ms 77768 KB Output is correct
4 Correct 1006 ms 77848 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1268 ms 79684 KB Output is correct
2 Correct 1560 ms 79784 KB Output is correct
3 Correct 954 ms 79748 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1389 ms 80108 KB Output is correct
2 Correct 2017 ms 80240 KB Output is correct
3 Correct 1861 ms 80028 KB Output is correct
4 Correct 2055 ms 80112 KB Output is correct
5 Correct 1997 ms 80140 KB Output is correct
6 Correct 1042 ms 80196 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 539 ms 69872 KB Output is correct
2 Correct 238 ms 38800 KB Output is correct

Subtask #14
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 714 ms 71808 KB Output is correct
2 Correct 860 ms 80480 KB Output is correct
3 Correct 641 ms 79996 KB Output is correct

Subtask #15
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 835 ms 72572 KB Output is correct
2 Correct 1321 ms 85868 KB Output is correct
3 Correct 1315 ms 85524 KB Output is correct
4 Correct 1182 ms 85508 KB Output is correct
5 Correct 744 ms 85764 KB Output is correct