#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), ssx(NS + 4);
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;
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;
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);
}
}
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;
}
vector<int> oy, ox;
for(int i = 1; i <= NS - 1; ++i){
if((int)x[i].size() >= 2 && ax[i] == -1) ax[i] = 1;
if(ax[i] == 1){
ox.push_back(i);
}
if(ay[i] == 1){
oy.push_back(i);
}
}
if((int)ox.size() + (int)oy.size() != n / 2){
cout << "NE"; return 0;
}
for(auto&i:oy){
ssx.push(1, 1, NS - 1, min(a[y[i][0]].first, a[y[i][1]].first), max(a[y[i][0]].first, a[y[i][1]].first), i);
}
for(auto&i:ox){
if(ssx.get(1, 1, NS - 1, i, min(a[x[i][0]].second, a[x[i][1]].second), max(a[x[i][0]].second, a[x[i][1]].second)) != -1){
cout << "NE"; return 0;
}
}
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;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
37 ms |
62948 KB |
Output is correct |
2 |
Correct |
38 ms |
62860 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
37 ms |
62948 KB |
Output is correct |
2 |
Correct |
38 ms |
62860 KB |
Output is correct |
3 |
Correct |
39 ms |
62880 KB |
Output is correct |
4 |
Correct |
38 ms |
62932 KB |
Output is correct |
5 |
Correct |
38 ms |
62916 KB |
Output is correct |
6 |
Correct |
38 ms |
62948 KB |
Output is correct |
7 |
Correct |
38 ms |
62916 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
37 ms |
62948 KB |
Output is correct |
2 |
Correct |
38 ms |
62860 KB |
Output is correct |
3 |
Correct |
39 ms |
62880 KB |
Output is correct |
4 |
Correct |
38 ms |
62932 KB |
Output is correct |
5 |
Correct |
38 ms |
62916 KB |
Output is correct |
6 |
Correct |
38 ms |
62948 KB |
Output is correct |
7 |
Correct |
38 ms |
62916 KB |
Output is correct |
8 |
Correct |
38 ms |
62896 KB |
Output is correct |
9 |
Correct |
39 ms |
62924 KB |
Output is correct |
10 |
Correct |
38 ms |
62968 KB |
Output is correct |
11 |
Correct |
40 ms |
62884 KB |
Output is correct |
12 |
Correct |
39 ms |
62972 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
37 ms |
62948 KB |
Output is correct |
2 |
Correct |
38 ms |
62860 KB |
Output is correct |
3 |
Correct |
39 ms |
62880 KB |
Output is correct |
4 |
Correct |
38 ms |
62932 KB |
Output is correct |
5 |
Correct |
38 ms |
62916 KB |
Output is correct |
6 |
Correct |
38 ms |
62948 KB |
Output is correct |
7 |
Correct |
38 ms |
62916 KB |
Output is correct |
8 |
Correct |
38 ms |
62896 KB |
Output is correct |
9 |
Correct |
39 ms |
62924 KB |
Output is correct |
10 |
Correct |
38 ms |
62968 KB |
Output is correct |
11 |
Correct |
40 ms |
62884 KB |
Output is correct |
12 |
Correct |
39 ms |
62972 KB |
Output is correct |
13 |
Correct |
43 ms |
63808 KB |
Output is correct |
14 |
Correct |
43 ms |
63788 KB |
Output is correct |
15 |
Correct |
44 ms |
63704 KB |
Output is correct |
16 |
Correct |
43 ms |
63856 KB |
Output is correct |
17 |
Correct |
43 ms |
63812 KB |
Output is correct |
18 |
Correct |
43 ms |
63792 KB |
Output is correct |
19 |
Correct |
43 ms |
63720 KB |
Output is correct |
20 |
Correct |
42 ms |
63772 KB |
Output is correct |
21 |
Correct |
43 ms |
63684 KB |
Output is correct |
22 |
Correct |
47 ms |
63756 KB |
Output is correct |
23 |
Correct |
45 ms |
63944 KB |
Output is correct |
24 |
Correct |
46 ms |
64068 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
37 ms |
62948 KB |
Output is correct |
2 |
Correct |
38 ms |
62860 KB |
Output is correct |
3 |
Correct |
39 ms |
62880 KB |
Output is correct |
4 |
Correct |
38 ms |
62932 KB |
Output is correct |
5 |
Correct |
38 ms |
62916 KB |
Output is correct |
6 |
Correct |
38 ms |
62948 KB |
Output is correct |
7 |
Correct |
38 ms |
62916 KB |
Output is correct |
8 |
Correct |
38 ms |
62896 KB |
Output is correct |
9 |
Correct |
39 ms |
62924 KB |
Output is correct |
10 |
Correct |
38 ms |
62968 KB |
Output is correct |
11 |
Correct |
40 ms |
62884 KB |
Output is correct |
12 |
Correct |
39 ms |
62972 KB |
Output is correct |
13 |
Correct |
43 ms |
63808 KB |
Output is correct |
14 |
Correct |
43 ms |
63788 KB |
Output is correct |
15 |
Correct |
44 ms |
63704 KB |
Output is correct |
16 |
Correct |
43 ms |
63856 KB |
Output is correct |
17 |
Correct |
43 ms |
63812 KB |
Output is correct |
18 |
Correct |
43 ms |
63792 KB |
Output is correct |
19 |
Correct |
43 ms |
63720 KB |
Output is correct |
20 |
Correct |
42 ms |
63772 KB |
Output is correct |
21 |
Correct |
43 ms |
63684 KB |
Output is correct |
22 |
Correct |
47 ms |
63756 KB |
Output is correct |
23 |
Correct |
45 ms |
63944 KB |
Output is correct |
24 |
Correct |
46 ms |
64068 KB |
Output is correct |
25 |
Correct |
297 ms |
93008 KB |
Output is correct |
26 |
Correct |
357 ms |
93744 KB |
Output is correct |
27 |
Correct |
284 ms |
92868 KB |
Output is correct |
28 |
Correct |
307 ms |
93124 KB |
Output is correct |
29 |
Correct |
244 ms |
92004 KB |
Output is correct |
30 |
Correct |
244 ms |
92228 KB |
Output is correct |
31 |
Correct |
286 ms |
92704 KB |
Output is correct |
32 |
Correct |
278 ms |
92596 KB |
Output is correct |
33 |
Correct |
248 ms |
89608 KB |
Output is correct |
34 |
Correct |
247 ms |
89916 KB |
Output is correct |
35 |
Correct |
198 ms |
88804 KB |
Output is correct |
36 |
Correct |
999 ms |
131240 KB |
Output is correct |
37 |
Correct |
348 ms |
102468 KB |
Output is correct |
38 |
Correct |
377 ms |
101904 KB |
Output is correct |