#include <bits/stdc++.h>
#define left_son (node<<1)
#define right_son ((node<<1)|1)
#define mid ((st+dr)>>1)
using namespace std;
const int Nmax = 1e6 + 5;
int n, N, M, money;
class SegmentTree
{
int lazy[Nmax<<2], L[Nmax<<2], R[Nmax<<2], best[Nmax<<2], mn[Nmax<<2];
public:
void update(int node, int st, int dr, int Left, int Right, int add)
{
if(Left<=st && dr<=Right)
{
mn[node] += add;
lazy[node] += add;
return;
}
if(lazy[node])
{
lazy[left_son] += lazy[node];
lazy[right_son] += lazy[node];
mn[left_son] += lazy[node];
mn[right_son] += lazy[node];
lazy[node] = 0;
}
if(Left<=mid) update(left_son, st, mid, Left, Right, add);
if(mid<Right) update(right_son, mid+1, dr, Left, Right, add);
mn[node] = min(mn[left_son], mn[right_son]);
if(L[node] == -1) return;
if(mn[left_son] == mn[right_son])
{
L[node] = L[left_son] + (L[left_son] == mid-st+1 ? L[right_son] : 0);
R[node] = R[right_son] + (R[right_son] == dr-mid ? R[left_son] : 0);
best[node] = max(best[left_son], best[right_son]);
best[node] = max(best[node], R[left_son] + L[right_son]);
}
else if(mn[node] == mn[left_son])
{
L[node] = L[left_son];
R[node] = 0;
best[node] = best[left_son];
}
else
{
L[node] = 0;
R[node] = R[right_son];
best[node] = best[right_son];
}
}
int query()
{
return mn[1] == 0 ? best[1] : 0;
}
int query2()
{
return mn[1];
}
void build(int node, int st, int dr, bool type = 0)
{
mn[node] = lazy[node] = 0;
if(!type) L[node] = R[node] = best[node] = dr-st+1;
else L[node] = -1;
if(st == dr) return;
build(left_son, st, mid);
build(right_son, mid+1, dr);
}
};
namespace solve0
{
vector< pair<int,int> > start[Nmax], finish[Nmax];
SegmentTree aint;
void compute()
{
int i, j, X1, Y1, X2, Y2, C;
int ans = 0;
aint.build(1, 1, M);
for(i=1; i<=n; ++i)
{
cin >> X1 >> Y1 >> X2 >> Y2 >> C;
start[X1].push_back({Y1, Y2});
finish[X2].push_back({Y1, Y2});
}
j = 0;
for(i=1; i<=N; ++i)
if(i==1 || !finish[i-1].empty())
{
for(auto e : finish[i-1])
aint.update(1, 1, M, e.first, e.second, -1);
while(j+1 <= N && aint.query() >= j-i+1)
{
++j;
for(auto e : start[j])
aint.update(1, 1, M, e.first, e.second, 1);
}
if(j == N && aint.query() >= N-i+1)
{
ans = max(ans, N-i+1);
break;
}
ans = max(ans, j-i);
}
cout << ans << '\n';
}
}
namespace solve1
{
int Cost[Nmax], X1[Nmax], X2[Nmax], Y1[Nmax], Y2[Nmax];
vector< pair< pair<int,int> , int > > event[Nmax];
SegmentTree aint;
int need(int L)
{
int i, ans = INT_MAX, x, y, ym;
for(i=1; i<=n; ++i) event[i].clear();
for(i=1; i<=n; ++i)
{
x = max(1, X1[i] - L + 1);
y = max(1, Y1[i] - L + 1);
ym = min(Y2[i], M - L + 1);
event[x].push_back({ {y, ym}, Cost[i] });
event[X2[i] + 1].push_back({ {y, ym}, -Cost[i] });
}
aint.build(1, 1, M-L+1, 1);
for(i=1; i<=N-L+1; ++i)
{
for(auto ev : event[i])
aint.update(1, 1, M-L+1, ev.first.first, ev.first.second, ev.second);
ans = min(ans, aint.query2());
}
return ans;
}
void compute()
{
int i;
for(i=1; i<=n; ++i) cin >> X1[i] >> Y1[i] >> X2[i] >> Y2[i] >> Cost[i];
int st = 1, dr = min(N, M);
while(st<=dr)
{
if(need(mid) <= money) st = mid+1;
else dr = mid-1;
}
cout << dr << '\n';
}
}
int main()
{
// freopen("input", "r", stdin);
// freopen("output", "w", stdout);
cin.sync_with_stdio(false);
cin >> N >> M >> money >> n;
if(!money) solve0 :: compute(); /// subtask 1 + 3
else solve1 :: compute(); /// subtask 2
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
71 ms |
70876 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
76 ms |
70888 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
67 ms |
70944 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
72 ms |
71696 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
73 ms |
76312 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
114 ms |
112032 KB |
Output is correct |
| 2 |
Correct |
137 ms |
112160 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
129 ms |
112160 KB |
Output is correct |
| 2 |
Correct |
122 ms |
112160 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
73 ms |
112160 KB |
Output is correct |
| 2 |
Runtime error |
137 ms |
143908 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
239 ms |
156772 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
252 ms |
187476 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
550 ms |
233348 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
308 ms |
233348 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1082 ms |
233348 KB |
Output is correct |
| 2 |
Correct |
427 ms |
233348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1514 ms |
233348 KB |
Output is correct |
| 2 |
Correct |
1463 ms |
233348 KB |
Output is correct |
| 3 |
Correct |
752 ms |
233348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1780 ms |
233348 KB |
Output is correct |
| 2 |
Correct |
2460 ms |
233348 KB |
Output is correct |
| 3 |
Correct |
2071 ms |
233348 KB |
Output is correct |
| 4 |
Correct |
1796 ms |
233348 KB |
Output is correct |
| 5 |
Correct |
1094 ms |
233348 KB |
Output is correct |
