#include <bits/stdc++.h>
#define int long long
#define umi(x, y) (x = min(x, y))
#define uma(x, y) (x = max(x, y))
using namespace std;
const int NS = (int)1e5 + 4;
int q[NS * 2][3], f, r;
struct Seg{
int n;
vector<set<int>> tree;
Seg(int N):n(N * 4){
tree.resize(n);
}
void push(int x, int s, int e, int ps, int pe, int val){
if(pe < s || ps > e) return;
if(ps <= s && pe >= e){
tree[x].insert(val);
return;
}
int m = (s + e) >> 1;
push(x * 2, s, m, ps, pe, val), push(x * 2 + 1, m + 1, e, ps, pe, val);
}
void era(int x, int s, int e, int es, int ee, int val){
if(ee < s || es > e) return;
if(es <= s && ee >= e){
tree[x].erase(val);
return;
}
int m = (s + e) >> 1;
era(x * 2, s, m, es, ee, val), era(x * 2 + 1, m + 1, e, es, ee, val);
}
int get(int x, int s, int e, int pos, int low, int high){
if(pos < s || pos > e) return -1;
auto p = tree[x].lower_bound(low);
int rv;
if(p == tree[x].end() || *p > high) rv = -1;
else rv = *p;
if(s < e){
int m = (s + e) >> 1;
uma(rv, max(get(x * 2, s, m, pos, low, high), get(x * 2 + 1, m + 1, e, pos, low, high)));
}
return rv;
}
};
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n; cin >> n;
vector<pair<int, int>> a(n);
vector<vector<int>> x(NS), y(NS);
for(int i = 0; i < n; ++i){
cin >> a[i].first >> a[i].second;
x[a[i].first].push_back(i), y[a[i].second].push_back(i);
}
vector<int> ax(NS, -1), ay(NS, -1);
Seg sx(NS + 4), sy(NS + 4);
int del = 0;
auto px = [&](int val, int col){
if(ax[val] == col){
cout << "NE"; exit(0);
}
if(ax[val] == -1){
ax[val] = 1 - col;
q[r][0] = x[val][0], q[r][1] = x[val][1], q[r++][2] = 1 - col;
if(del) sy.era(1, 1, NS - 1, min(a[x[val][0]].second, a[x[val][1]].second), max(a[x[val][0]].second, a[x[val][1]].second), val);
}
};
auto py = [&](int val, int col){
if(ay[val] == col){
cout << "NE"; exit(0);
}
if(ay[val] == -1){
ay[val] = 1 - col;
q[r][0] = y[val][0], q[r][1] = y[val][1], q[r++][2] = 1 - col;
if(del) sx.era(1, 1, NS - 1, min(a[y[val][0]].first, a[y[val][1]].first), max(a[y[val][0]].first, a[y[val][1]].first), val);
}
};
for(int i = 1; i < NS; ++i){
if((int)x[i].size() >= 2){
int va = a[x[i][0]].second, vb = a[x[i][1]].second;
sy.push(1, 1, NS - 1, min(va, vb), max(va, vb), i);
}
if((int)y[i].size() >= 2){
int va = a[y[i][0]].first, vb = a[y[i][1]].first;
sx.push(1, 1, NS - 1, min(va, vb), max(va, vb), i);
}
}
for(int i = 0; i < n; ++i){
if((int)x[a[i].first].size() + (int)y[a[i].second].size() == 2){
cout << "NE"; return 0;
}
if((int)x[a[i].first].size() == 1){
py(a[i].second, 0);
}
else if((int)y[a[i].second].size() == 1){
px(a[i].first, 0);
}
}
del = 1;
while(f < r){
int nx = q[f][0], ny = q[f][1], num = q[f][2];
if(a[nx].first == a[ny].first){
while(true){
int mn = min(a[nx].second, a[ny].second), mx = max(a[nx].second, a[ny].second);
int val = sx.get(1, 1, NS - 1, a[nx].first, mn, mx);
if(val != -1){
py(val, num);
}
else break;
}
}
else{
while(true){
int mn = min(a[nx].first, a[ny].first), mx = max(a[nx].first, a[ny].first);
int val = sy.get(1, 1, NS - 1, a[ny].second, mn, mx);
if(val != -1){
px(val, num);
}
else break;
}
}
++f;
}
cout << "DA\n";
for(int i = 1; i <= NS - 1; ++i){
if((int)x[i].size() >= 2 && ax[i] == -1) ax[i] = 1;
if(ax[i] == 1){
cout << x[i][0] + 1 << ' ' << x[i][1] + 1 << '\n';
}
if(ay[i] == 1){
cout << y[i][0] + 1 << ' ' << y[i][1] + 1 << '\n';
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
44108 KB |
Output is correct |
| 2 |
Correct |
23 ms |
44112 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
44108 KB |
Output is correct |
| 2 |
Correct |
23 ms |
44112 KB |
Output is correct |
| 3 |
Correct |
23 ms |
44176 KB |
Output is correct |
| 4 |
Correct |
23 ms |
44076 KB |
Output is correct |
| 5 |
Correct |
24 ms |
44108 KB |
Output is correct |
| 6 |
Execution timed out |
2598 ms |
44176 KB |
Time limit exceeded |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
44108 KB |
Output is correct |
| 2 |
Correct |
23 ms |
44112 KB |
Output is correct |
| 3 |
Correct |
23 ms |
44176 KB |
Output is correct |
| 4 |
Correct |
23 ms |
44076 KB |
Output is correct |
| 5 |
Correct |
24 ms |
44108 KB |
Output is correct |
| 6 |
Execution timed out |
2598 ms |
44176 KB |
Time limit exceeded |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
44108 KB |
Output is correct |
| 2 |
Correct |
23 ms |
44112 KB |
Output is correct |
| 3 |
Correct |
23 ms |
44176 KB |
Output is correct |
| 4 |
Correct |
23 ms |
44076 KB |
Output is correct |
| 5 |
Correct |
24 ms |
44108 KB |
Output is correct |
| 6 |
Execution timed out |
2598 ms |
44176 KB |
Time limit exceeded |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
44108 KB |
Output is correct |
| 2 |
Correct |
23 ms |
44112 KB |
Output is correct |
| 3 |
Correct |
23 ms |
44176 KB |
Output is correct |
| 4 |
Correct |
23 ms |
44076 KB |
Output is correct |
| 5 |
Correct |
24 ms |
44108 KB |
Output is correct |
| 6 |
Execution timed out |
2598 ms |
44176 KB |
Time limit exceeded |
| 7 |
Halted |
0 ms |
0 KB |
- |
