제출 #118797

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
118797		eriksuenderhauf	Pyramid Base (IOI08_pyramid_base)	C++11	70 / 100	5102 ms	146184 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*4], lazy[MAXN*4];

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);
		//cerr << l << " " << r << " " << k << " " << seg[k] << " " << v << " !!!\n";
		return;
	}
	int m = (l+r) / 2;
	//if (a <= m)
		upd(l, m, k*2, a, b, v);
	//if (m < b)
		upd(m+1, r, k*2+1, a, b, v);
	//cerr << l << " " << r << " " << k << " " << seg[k] << " " << v << "\n";
	seg[k] = min(seg[k*2], seg[k*2+1]);
	//cerr << l << " " << r << " " << k << " " << seg[k] << " " << v << "\n";
	//cerr << "\n";
}

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) {
	//cerr << "check size: " << w << "\n";
	mem(vis, 0);
	//mem(seg, 0x3f);
	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) {
			//cerr << "insert: " << cur.loc.fi << "->" << cur.loc.se << " at position: " << cur.pos << " cost: " << cur.cost << "\n";
			upd(1, n, 1, cur.loc.fi, cur.loc.se, cur.cost);
		} else if (cur.t == 1) {
			vis[cur.pos] = 1;
			//cerr << "qry: " << cur.pos << ": " << seg[1]  << " " << seg[2] << " " << seg[3] << "\n";
			ret = min(ret, qry(1, n, 1, 1, n-w+1));
		} else {
			//cerr << "erase: " << cur.loc.fi << "->" << cur.loc.se << " at position: " << cur.pos << " cost: " << cur.cost << "\n";
			upd(1, n, 1, cur.loc.fi, cur.loc.se, cur.cost);
		}
	}
	//cerr << "\n";
	return ret;
}

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);
	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;
}

컴파일 시 표준 에러 (stderr) 메시지

pyramid_base.cpp: In function 'll f(int)':
pyramid_base.cpp:113: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 main()':
pyramid_base.cpp:134: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:136: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: 0 / 10
• Subtask 14: 0 / 10
• Subtask 15: 0 / 10