#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<int, int> pii;
typedef pair<ld, ld> pld;
struct rect{
int x1, y1, x2, y2;
};
int lazy[800009];
pii seg[800009];
void push(int v){
seg[2*v].ff += lazy[v];
seg[2*v+1].ff += lazy[v];
lazy[2*v] += lazy[v];
lazy[2*v+1] += lazy[v];
lazy[v] = 0;
}
void upd(int v, int tl, int tr, int l, int r, int val){
if(r < tl || tr < l)
return;
if(l <= tl && tr <= r){
seg[v].ff += val;
lazy[v] += val;
}
else{
push(v);
upd(2*v, tl, (tl+tr)/2, l, r, val);
upd(2*v+1, (tl+tr)/2+1, tr, l, r, val);
seg[v] = max(seg[2*v], seg[2*v+1]);
}
}
void build(int v, int tl, int tr){
if(tl == tr){
seg[v] = {0, tl};
return;
}
build(2*v, tl, (tl+tr)/2);
build(2*v+1, (tl+tr)/2+1, tr);
seg[v] = max(seg[2*v], seg[2*v+1]);
}
vector<int> ycord;
vector<int> xcord;
int yc(int x){return lower_bound(ycord.begin(), ycord.end(), x)-ycord.begin();}
int xc(int x){return lower_bound(xcord.begin(), xcord.end(), x)-xcord.begin();}
vector<pii> add[400009];
vector<pii> del[400009];
int n, k;
rect ar[200009];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
cin >> n >> k;
for(int i = 0; i < n; ++i){
cin >> ar[i].x1 >> ar[i].y1 >> ar[i].x2 >> ar[i].y2;
ycord.pb(ar[i].y1);
ycord.pb(ar[i].y2);
xcord.pb(ar[i].x1);
xcord.pb(ar[i].x2);
}
sort(ycord.begin(), ycord.end());
ycord.resize(unique(ycord.begin(), ycord.end())-ycord.begin());
sort(xcord.begin(), xcord.end());
xcord.resize(unique(xcord.begin(), xcord.end())-xcord.begin());
for(int i = 0; i < n; ++i)
ar[i] = {xc(ar[i].x1), yc(ar[i].y1), xc(ar[i].x2), yc(ar[i].y2)};
vector<pii> ans;
while(k--){
build(1, 0, ycord.size()-1);
for(int i = 0; i < n; ++i)
if(ar[i].x1 >= 0){
add[ar[i].x1].pb({ar[i].y1, ar[i].y2});
del[ar[i].x2].pb({ar[i].y1, ar[i].y2});
}
pair<int, pii> curans = {0, {0, 0}};
for(int i = 0; i < xcord.size(); ++i){
for(auto u : add[i])
upd(1, 0, ycord.size()-1, u.ff, u.ss, 1);
curans = max(curans, {seg[1].ff, {i, seg[1].ss}});
for(auto u : del[i])
upd(1, 0, ycord.size()-1, u.ff, u.ss, -1);
add[i].clear();
del[i].clear();
}
ans.pb(curans.ss);
pii pt = curans.ss;
for(int i = 0; i < n; ++i)
if(ar[i].x1 <= pt.ff && pt.ff <= ar[i].x2 && ar[i].y1 <= pt.ss && pt.ss <= ar[i].y2)
ar[i] = {-1, -1, -1, -1};
}
for(int i = 0; i < n; ++i)
assert(ar[i].x1 < 0);
for(auto u : ans)
cout << xcord[u.ff] << ' ' << ycord[u.ss] << '\n';
}
Compilation message
hamburg.cpp: In function 'int main()':
hamburg.cpp:88:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
88 | for(int i = 0; i < xcord.size(); ++i){
| ~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
19456 KB |
Output is correct |
| 2 |
Correct |
18 ms |
19456 KB |
Output is correct |
| 3 |
Correct |
18 ms |
19456 KB |
Output is correct |
| 4 |
Correct |
20 ms |
19456 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
51 ms |
39160 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 |
51 ms |
39160 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 |
51 ms |
39160 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 |
19 ms |
19456 KB |
Output is correct |
| 2 |
Correct |
18 ms |
19456 KB |
Output is correct |
| 3 |
Correct |
18 ms |
19456 KB |
Output is correct |
| 4 |
Correct |
20 ms |
19456 KB |
Output is correct |
| 5 |
Runtime error |
491 ms |
93300 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
51 ms |
39160 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 |
51 ms |
39160 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 |
51 ms |
39160 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
