| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1144393 | arashmemar | Pyramid Base (IOI08_pyramid_base) | C++17 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 100;
long long int inf = 3e9;
int n, m;
long long int cnt;
vector <pair <long long int, pair <int, int>>> add[4 * maxn], rem[4 * maxn];
vector <pair <pair <pair <int, int>, pair <int, int>>, int>> ps;
long long int v[4 * maxn], lazy[4 * maxn];
struct Node
{
void spread(int id, int L, int R)
{
cnt++;
v[id] += lazy[id];
if (id * 2 < 4 * maxn)
{
lazy[id * 2 + 0] += lazy[id];
lazy[id * 2 + 1] += lazy[id];
}
lazy[id] = 0;
return ;
}
void updatep(int id, int L, int R, int l, int r, long long int val)
{
cnt++;
spread(id, L, R);
if (L == l and R == r)
{
lazy[id] = val;
spread(id, L, R);
return ;
}
int mid = (L + R) / 2;
if (l < mid)
{
updatep(id * 2 + 0, L, mid, l, min(mid, r), val);
}
if (r > mid)
{
updatep(id * 2 + 1, mid, R, max(l, mid), r, val);
}
spread(id * 2 + 0, L, mid);
spread(id * 2 + 1, mid, R);
v[id] = min(v[id * 2 + 0], v[id * 2 + 1]);
return ;
}
long long int get()
{
cnt++;
return v[1];
}
};
Node *root;
pair <int, int> update(int id, int L, int R, int l, int r)
{
if (L == l and R == r)
{
return {id, id};
}
int mid = (L + R) / 2;
pair <int, int> ret, tmp;
ret = tmp = {0, 0};
if (l < mid)
{
ret = update(id * 2 + 0, L, mid, l, min(r, mid));
}
if (r > mid)
{
tmp = update(id * 2 + 1, mid, R, max(l, mid), r);
ret.second = tmp.second;
if (ret.first == 0)
{
ret.first = tmp.first;
}
}
return ret;
}
void inc(int id)
{
for (auto o : add[id])
{
cnt++;
root->updatep(1, 1, n + 1, o.second.first, o.second.second, o.first);
}
return ;
}
void del(int id)
{
for (auto o : rem[id])
{
cnt++;
root->updatep(1, 1, n + 1, o.second.first, o.second.second, -o.first);
}
return ;
}
long long int get(int id, int L, int R)
{
cnt++;
inc(id);
if (R - L == 1)
{
long long int ret = root->get();
del(id);
return ret;
}
int mid = (L + R) / 2;
long long int tmp1 = get(id * 2 + 0, L, mid);
long long int tmp2 = get(id * 2 + 1, mid, R);
long long int ret = min(tmp1, tmp2);
del(id);
return ret;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int b, p;
cin >> m >> n >> b >> p;
unsigned int a = 0;
root = new Node();
int l = 0, r = min(n, m) + 1;
for (int i = 0;i < p;i++)
{
int x1, y1, x2, y2, c;
cin >> x1 >> y1 >> x2 >> y2 >> c;
ps.push_back({{{y1, y2}, {x1, x2}}, c});
}
while (r - l > 1)
{
int mid = (l + r) / 2;
for (auto o : ps)
{
int y1 = o.first.first.first, y2 = o.first.first.second, x1 = o.first.second.first, x2 = o.first.second.second, c = o.second;
pair <int, int> tmp = update(1, 1, m + 1, max(1, x1 - mid + 1), x2 + 1);
add[tmp.first].push_back({c, {max(1, y1 - mid + 1), y2 + 1}});
rem[tmp.second].push_back({c, {max(1, y1 - mid + 1), y2 + 1}});
}
if (mid > 1)
{
int y1 = m - mid + 2, y2 = m, x1 = 1, x2 = n;
long long int c = inf;
pair <int, int> tmp = update(1, 1, m + 1, y1, y2 + 1);
add[tmp.first].push_back({c, {x1, x2 + 1}});
rem[tmp.second].push_back({c, {x1, x2 + 1}});
y1 = 1, y2 = m, x1 = n - mid + 2, x2 = n;
tmp = update(1, 1, m + 1, y1, y2 + 1);
add[tmp.first].push_back({c, {x1, x2 + 1}});
rem[tmp.second].push_back({c, {X1, x2 + 1}});
}
long long int tmp = get(1, 1, m + 1);
if (tmp <= b)
{
l = mid;
}
else
{
r = mid;
}
for (int i = 0;i <= 4 * m;i++)
{
add[i].clear();
rem[i].clear();
v[i] = lazy[i] = 0;
}
}
cout << l;
return 0;
}