This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define pii pair<ll,ll>
#define f first
#define s second
#define ll long long int
const int mxP = 4e5;
const int mxN = 1e6;
int n,m;
ll segtree[4*mxN+1];
ll laz[4*mxN+1];
int curr;
void build(int l = 0, int r = n-1, int idx = 0){
if (r+1<curr){
segtree[idx] = 2e9+1;
laz[idx] = 0;
return;
}
segtree[idx] = 0;
laz[idx] = 0;
if (l == r) return;
int m = (l+r)/2;
build(l,m,2*idx+1);
build(m+1,r,2*idx+2);
}
void upd(int tl, int tr, ll v, int l = 0, int r = n-1, int idx = 0){
if (l > tr || r < tl || r+1<curr) return;
if (l >= tl && r <= tr){
laz[idx] += v;
return;
}
int m = (l+r)/2;
upd(tl,tr,v,l,m,2*idx+1);
upd(tl,tr,v,m+1,r,2*idx+2);
segtree[idx] = min(segtree[2*idx+1]+laz[2*idx+1],segtree[2*idx+2]+laz[2*idx+2]);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll b;
int p;
cin >> m >> n >> b >> p;
pii x[p];
pii y[p];
ll c[p];
ll x1,y1,x2,y2,c1;
for (int i =0; i < p; i++){
cin >> x1 >> y1 >> x2 >> y2 >> c1;
x1 -= 1;
y1 -= 1;
x2 -= 1;
y2 -= 1;
x[i] = {x1,x2};
y[i] = {y1,y2};
c[i] = c1;
}
int start = 0;
int end = min(n,m)+1;
bool w;
ll best;
bool vis[p];
int last;
while (end - start > 1){
curr = (start+end)/2;
build();
memset(vis,0,sizeof(vis));
priority_queue<pii, vector<pii>, greater<pii>> queue;
for (int i = 0; i < p; i++){
queue.push({x[i].f,i});
queue.push({x[i].s+curr,i});
}
w = false;
last = -1;
while (queue.size() > 0){
pii cur = queue.top();
queue.pop();
if (cur.f >= m) break;
best = laz[0]+segtree[0];
if (last != cur.f && best <= b && cur.f >= curr){
w = true;
break;
}
last = cur.f;
ll val = c[cur.s];
if (vis[cur.s]) val *= -1;
else vis[cur.s] = 1;
upd(y[cur.s].f,min((ll) n-1,y[cur.s].s+curr-1),val);
}
best = laz[0]+segtree[0];
if (best <= b) w = true;
if (w) start = curr;
else end = curr;
}
cout << start << "\n";
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |