oj.uz

Submission #118797

# Submission time Handle Problem Language Result Execution time Memory
118797 2019-06-19T18:55:10 Z eriksuenderhauf Pyramid Base (IOI08_pyramid_base) C++11
70 / 100
 5000 ms 146184 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*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;
}

Compilation message

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

# Verdict Execution time Memory Grader output
1 Correct 23 ms 27772 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 27776 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 27896 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 28448 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 32032 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 44240 KB Output is correct
2 Correct 96 ms 58976 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 59352 KB Output is correct
2 Correct 66 ms 45040 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 29224 KB Output is correct
2 Correct 132 ms 29156 KB Output is correct
3 Correct 188 ms 29164 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 653 ms 35056 KB Output is correct
2 Correct 615 ms 34916 KB Output is correct
3 Correct 474 ms 34944 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1163 ms 64268 KB Output is correct
2 Correct 138 ms 31184 KB Output is correct
3 Correct 522 ms 64120 KB Output is correct
4 Correct 1479 ms 64556 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1614 ms 66388 KB Output is correct
2 Correct 1535 ms 66400 KB Output is correct
3 Correct 1162 ms 66444 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1672 ms 66924 KB Output is correct
2 Correct 2142 ms 66916 KB Output is correct
3 Correct 2062 ms 67028 KB Output is correct
4 Correct 2057 ms 66956 KB Output is correct
5 Correct 2052 ms 66872 KB Output is correct
6 Correct 1300 ms 67024 KB Output is correct

Subtask #13
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5102 ms 105296 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #14
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5083 ms 115144 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #15
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5091 ms 146184 KB Time limit exceeded
2 Halted 0 ms 0 KB -