#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
#define endl '\n'
#define pi pair<int, int>
#define f first
#define s second
struct rect{
int x, y, X, Y;
};
const int maxn = 200000;
int n, m, k;
int sz[4];
int cnt[maxn];
vector<rect> a;
vector<int> id;
vector<vector<int>> rin[4], rot[4];
int idx(int x){
return lower_bound(id.begin(), id.end(), x) - id.begin();
}
rect bnd(vector<rect> v){
rect ret = {m, m, 0, 0};
for(rect i : v){
ret.x = min(ret.x, i.X);
ret.y = min(ret.y, i.Y);
ret.X = max(ret.X, i.x);
ret.Y = max(ret.Y, i.y);
}
return ret;
}
bool crs(int a, int b, int c){
return a <= b && b <= c;
}
vector<pi> solve(vector<rect> v, int x){
rect f = bnd(v);
if(x == 1){
if(f.x < f.X || f.y < f.Y) return {};
else return {{f.x, f.y}};
}
vector<pi> pt = {{f.x, f.y}, {f.x, f.Y}, {f.X, f.y}, {f.X, f.Y}};
for(pi p : pt){
vector<rect> nv;
for(rect i : v){
if(!crs(i.x, p.f, i.X) || !crs(i.y, p.s, i.Y)) nv.push_back(i);
}
vector<pi> ret = solve(nv, x - 1);
if(!ret.empty()){
ret.push_back(p);
return ret;
}
}
return {};
}
int cur;
void add(int x){
if(!cnt[x]) cur++;
cnt[x]++;
}
void del(int x){
if(cnt[x] == 1) cur--;
cnt[x]--;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> k;
a.resize(n);
for(int i = 0; i < n; i++){
cin >> a[i].x >> a[i].y >> a[i].X >> a[i].Y;
id.push_back(a[i].x);
id.push_back(a[i].y);
id.push_back(a[i].X);
id.push_back(a[i].Y);
}
sort(id.begin(), id.end());
id.erase(unique(id.begin(), id.end()), id.end());
m = id.size();
for(int i = 0; i < n; i++){
a[i].x = idx(a[i].x);
a[i].y = idx(a[i].y);
a[i].X = idx(a[i].X);
a[i].Y = idx(a[i].Y);
}
vector<pi> ans = solve(a, k);
if(!ans.empty()){
for(pi i : ans) cout << id[i.f] << " " << id[i.s] << endl;
return 0;
}
rect f = bnd(a);
sz[0] = sz[2] = f.X - f.x + 1, sz[1] = sz[3] = f.Y - f.y + 1;
for(int i = 0; i < 4; i++){
rin[i].resize(sz[i]);
rot[i].resize(sz[i]);
}
for(int i = 0; i < n; i++){
if(crs(a[i].y, f.y, a[i].Y)){
rin[0][max(0, a[i].x - f.x)].push_back(i);
rot[0][min(sz[0] - 1, a[i].X - f.x)].push_back(i);
}
if(crs(a[i].x, f.X, a[i].X)){
rin[1][max(0, a[i].y - f.y)].push_back(i);
rot[1][min(sz[1] - 1, a[i].Y - f.y)].push_back(i);
}
if(crs(a[i].y, f.Y, a[i].Y)){
rin[2][max(0, f.X - a[i].X)].push_back(i);
rot[2][min(sz[2] - 1, f.X - a[i].x)].push_back(i);
}
if(crs(a[i].x, f.x, a[i].X)){
rin[3][max(0, f.Y - a[i].Y)].push_back(i);
rot[3][min(sz[3] - 1, f.Y - a[i].y)].push_back(i);
}
}
for(int it[4] = {0, -1, -1, -1}; it[0] < sz[0]; it[0]++){
for(int j : rin[0][it[0]]) add(j);
for(int t = 1; t < 4; t++){
while(it[t] < sz[t] - 1){
if(it[t] != -1){
bool w = 1;
for(int j : rot[t][it[t]]){
if(cnt[j] == 1){
w = 0;
break;
}
}
if(!w) break;
for(int j : rot[t][it[t]]) del(j);
}
it[t]++;
for(int j : rin[t][it[t]]) add(j);
}
}
if(cur == n){
cout << id[it[0] + f.x] << " " << id[f.y] << endl;
cout << id[f.X] << " " << id[it[1] + f.y] << endl;
cout << id[f.X - it[2]] << " " << id[f.Y] << endl;
cout << id[f.x] << " " << id[f.Y - it[3]] << endl;
break;
}
for(int j : rot[0][it[0]]) del(j);
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
512 KB |
Output is correct |
2 |
Correct |
3 ms |
512 KB |
Output is correct |
3 |
Correct |
3 ms |
512 KB |
Output is correct |
4 |
Correct |
3 ms |
512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
512 KB |
Output is correct |
2 |
Correct |
3 ms |
512 KB |
Output is correct |
3 |
Correct |
3 ms |
512 KB |
Output is correct |
4 |
Correct |
3 ms |
512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
512 KB |
Output is correct |
2 |
Correct |
3 ms |
512 KB |
Output is correct |
3 |
Correct |
3 ms |
512 KB |
Output is correct |
4 |
Correct |
3 ms |
512 KB |
Output is correct |
5 |
Correct |
3 ms |
512 KB |
Output is correct |
6 |
Correct |
3 ms |
512 KB |
Output is correct |
7 |
Correct |
3 ms |
512 KB |
Output is correct |
8 |
Correct |
3 ms |
512 KB |
Output is correct |
9 |
Correct |
3 ms |
624 KB |
Output is correct |
10 |
Correct |
4 ms |
512 KB |
Output is correct |
11 |
Correct |
3 ms |
512 KB |
Output is correct |
12 |
Correct |
3 ms |
512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
512 KB |
Output is correct |
2 |
Correct |
3 ms |
512 KB |
Output is correct |
3 |
Correct |
3 ms |
512 KB |
Output is correct |
4 |
Correct |
4 ms |
512 KB |
Output is correct |
5 |
Correct |
3 ms |
512 KB |
Output is correct |
6 |
Correct |
3 ms |
512 KB |
Output is correct |
7 |
Correct |
3 ms |
512 KB |
Output is correct |
8 |
Correct |
3 ms |
512 KB |
Output is correct |
9 |
Correct |
3 ms |
512 KB |
Output is correct |
10 |
Correct |
3 ms |
512 KB |
Output is correct |
11 |
Correct |
3 ms |
512 KB |
Output is correct |
12 |
Correct |
3 ms |
512 KB |
Output is correct |
13 |
Correct |
5 ms |
640 KB |
Output is correct |
14 |
Incorrect |
5 ms |
1076 KB |
Unexpected end of file - int32 expected |
15 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
512 KB |
Output is correct |
2 |
Correct |
3 ms |
512 KB |
Output is correct |
3 |
Correct |
3 ms |
512 KB |
Output is correct |
4 |
Correct |
3 ms |
512 KB |
Output is correct |
5 |
Correct |
326 ms |
12936 KB |
Output is correct |
6 |
Correct |
330 ms |
12948 KB |
Output is correct |
7 |
Correct |
330 ms |
12984 KB |
Output is correct |
8 |
Correct |
330 ms |
13068 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
512 KB |
Output is correct |
2 |
Correct |
3 ms |
512 KB |
Output is correct |
3 |
Correct |
3 ms |
512 KB |
Output is correct |
4 |
Correct |
3 ms |
512 KB |
Output is correct |
5 |
Correct |
334 ms |
14280 KB |
Output is correct |
6 |
Correct |
354 ms |
13872 KB |
Output is correct |
7 |
Correct |
344 ms |
14256 KB |
Output is correct |
8 |
Correct |
344 ms |
17128 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
512 KB |
Output is correct |
2 |
Correct |
3 ms |
512 KB |
Output is correct |
3 |
Correct |
3 ms |
512 KB |
Output is correct |
4 |
Correct |
3 ms |
512 KB |
Output is correct |
5 |
Correct |
3 ms |
512 KB |
Output is correct |
6 |
Correct |
3 ms |
512 KB |
Output is correct |
7 |
Correct |
3 ms |
512 KB |
Output is correct |
8 |
Correct |
3 ms |
512 KB |
Output is correct |
9 |
Correct |
3 ms |
624 KB |
Output is correct |
10 |
Correct |
4 ms |
512 KB |
Output is correct |
11 |
Correct |
3 ms |
512 KB |
Output is correct |
12 |
Correct |
3 ms |
512 KB |
Output is correct |
13 |
Correct |
341 ms |
14896 KB |
Output is correct |
14 |
Correct |
374 ms |
14664 KB |
Output is correct |
15 |
Correct |
337 ms |
13072 KB |
Output is correct |
16 |
Correct |
344 ms |
13028 KB |
Output is correct |
17 |
Correct |
346 ms |
16560 KB |
Output is correct |
18 |
Correct |
345 ms |
13032 KB |
Output is correct |
19 |
Correct |
340 ms |
16992 KB |
Output is correct |
20 |
Correct |
353 ms |
17628 KB |
Output is correct |
21 |
Correct |
428 ms |
26092 KB |
Output is correct |
22 |
Correct |
386 ms |
18448 KB |
Output is correct |
23 |
Correct |
401 ms |
21164 KB |
Output is correct |
24 |
Correct |
442 ms |
24328 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
512 KB |
Output is correct |
2 |
Correct |
3 ms |
512 KB |
Output is correct |
3 |
Correct |
3 ms |
512 KB |
Output is correct |
4 |
Correct |
4 ms |
512 KB |
Output is correct |
5 |
Correct |
3 ms |
512 KB |
Output is correct |
6 |
Correct |
3 ms |
512 KB |
Output is correct |
7 |
Correct |
3 ms |
512 KB |
Output is correct |
8 |
Correct |
3 ms |
512 KB |
Output is correct |
9 |
Correct |
3 ms |
512 KB |
Output is correct |
10 |
Correct |
3 ms |
512 KB |
Output is correct |
11 |
Correct |
3 ms |
512 KB |
Output is correct |
12 |
Correct |
3 ms |
512 KB |
Output is correct |
13 |
Correct |
5 ms |
640 KB |
Output is correct |
14 |
Incorrect |
5 ms |
1076 KB |
Unexpected end of file - int32 expected |
15 |
Halted |
0 ms |
0 KB |
- |