#include <cstdio>
#include <algorithm>
#include <queue>
#define m ((s + e)>>1)
using namespace std;
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
const int INF = 10000000;
ii lca(int s,int e,int l,int r,int pos){
if (r<=m && m<pos) return ii(s,e);
else if (pos<=m && m<l) return ii(s,e);
if (pos<=m) return lca(s,m,l,r,pos);
else return lca(m+1,e,l,r,pos);
}
struct minnode{
int s,e;
ii val=ii(INF, -1);
minnode *l=nullptr,*r=nullptr;
minnode (int _s,int _e){
s=_s,e=_e;
}
bool inside(int i){
return s<=i && i<=e;
}
void update(int i,ii j){
if (s==e) val=j;
else{
if (i<=m){
if (l==nullptr) l=new minnode(i,i);
else if (!l->inside(i)){
minnode *temp=l;
ii child=lca(s,e,l->s,l->e,i);
l=new minnode(child.first,child.second);
if (temp->e<=(l->s+l->e)>>1) l->l=temp;
else l->r=temp;
}
l->update(i,j);
}
else{
if (r==nullptr) r=new minnode(i,i);
else if (!r->inside(i)){
minnode *temp=r;
ii child=lca(s,e,r->s,r->e,i);
r=new minnode(child.first,child.second);
if (temp->e<=(r->s+r->e)>>1) r->l=temp;
else r->r=temp;
}
r->update(i,j);
}
val=min((l==nullptr)?ii(INF,-1):l->val,(r==nullptr)?ii(INF,-1):r->val);
}
}
ii query(int i,int j){
if (i<=s && e<=j) return val;
else if (j<=m) return (l==nullptr)?ii(INF,-1):l->query(i,j);
else if (m<i) return (r==nullptr)?ii(INF,-1):r->query(i,j);
else return min((l==nullptr)?ii(INF,-1):l->query(i,m),(r==nullptr)?ii(INF,-1):r->query(m+1,j));
}
minnode* clone(){
minnode* res=new minnode(s,e);
res->val=val;
res->l=(l==nullptr)?nullptr:l->clone();
res->r=(r==nullptr)?nullptr:r->clone();
return res;
}
};
struct minnode2d{
int s,e;
minnode *val=new minnode(1,100000);
minnode2d *l=nullptr,*r=nullptr;
minnode2d (int _s,int _e){
s=_s,e=_e;
}
bool inside(int i){
return s<=i && i<=e;
}
void update(int i,int j,ii k){
if (s==e) val->update(j,k);
else{
if (i<=m){
if (l==nullptr) l=new minnode2d(i,i);
else if (!l->inside(i)){
minnode2d *temp=l;
ii child=lca(s,e,l->s,l->e,i);
l=new minnode2d(child.first,child.second);
if (temp->e<=(l->s+l->e)>>1) l->l=temp;
else l->r=temp;
l->val=temp->val->clone();
}
l->update(i,j,k);
}
else{
if (r==nullptr) r=new minnode2d(i,i);
else if (!r->inside(i)){
minnode2d *temp=r;
ii child=lca(s,e,r->s,r->e,i);
r=new minnode2d(child.first,child.second);
if (temp->e<=(r->s+r->e)>>1) r->l=temp;
else r->r=temp;
r->val=temp->val->clone();
}
r->update(i,j,k);
}
val->update(j,min((l==nullptr)?ii(INF,-1):l->val->query(j,j),(r==nullptr)?ii(INF,-1):r->val->query(j,j)));
}
}
ii query(int i,int j,int i2,int j2){
if (i<=s && e<=j) return val->query(i2,j2);
else if (j<=m) return (l==nullptr)?ii(INF,-1):l->query(i,j,i2,j2);
else if (m<i) return (r==nullptr)?ii(INF,-1):r->query(i,j,i2,j2);
else return min((l==nullptr)?ii(INF,-1):l->query(i,m,i2,j2),(r==nullptr)?ii(INF,-1):r->query(m+1,j,i2,j2));
}
};
struct maxnode{
int s,e;
ii val=ii(0,-1);
maxnode *l=nullptr,*r=nullptr;
maxnode (int _s,int _e){
s=_s,e=_e;
}
bool inside(int i){
return s<=i && i<=e;
}
void update(int i,ii j){
if (s==e) val=j;
else{
if (i<=m){
if (l==nullptr) l=new maxnode(i,i);
else if (!l->inside(i)){
maxnode *temp=l;
ii child=lca(s,e,l->s,l->e,i);
l=new maxnode(child.first,child.second);
if (temp->e<=(l->s+l->e)>>1) l->l=temp;
else l->r=temp;
}
l->update(i,j);
}
else{
if (r==nullptr) r=new maxnode(i,i);
else if (!r->inside(i)){
maxnode *temp=r;
ii child=lca(s,e,r->s,r->e,i);
r=new maxnode(child.first,child.second);
if (temp->e<=(r->s+r->e)>>1) r->l=temp;
else r->r=temp;
}
r->update(i,j);
}
val=max((l==nullptr)?ii(0,-1):l->val,(r==nullptr)?ii(0,-1):r->val);
}
}
ii query(int i,int j){
if (i<=s && e<=j) return val;
else if (j<=m) return (l==nullptr)?ii(0,-1):l->query(i,j);
else if (m<i) return (r==nullptr)?ii(0,-1):r->query(i,j);
else return max((l==nullptr)?ii(0,-1):l->query(i,m),(r==nullptr)?ii(0,-1):r->query(m+1,j));
}
maxnode* clone(){
maxnode* res=new maxnode(s,e);
res->val=val;
res->l=(l==nullptr)?nullptr:l->clone();
res->r=(r==nullptr)?nullptr:r->clone();
return res;
}
};
struct maxnode2d{
int s,e;
maxnode *val=new maxnode(1,100000);
maxnode2d *l=nullptr,*r=nullptr;
maxnode2d (int _s,int _e){
s=_s,e=_e;
}
bool inside(int i){
return s<=i && i<=e;
}
void update(int i,int j,ii k){
if (s==e) val->update(j,k);
else{
if (i<=m){
if (l==nullptr) l=new maxnode2d(i,i);
else if (!l->inside(i)){
maxnode2d *temp=l;
ii child=lca(s,e,l->s,l->e,i);
l=new maxnode2d(child.first,child.second);
if (temp->e<=(l->s+l->e)>>1) l->l=temp;
else l->r=temp;
l->val=temp->val->clone();
}
l->update(i,j,k);
}
else{
if (r==nullptr) r=new maxnode2d(i,i);
else if (!r->inside(i)){
maxnode2d *temp=r;
ii child=lca(s,e,r->s,r->e,i);
r=new maxnode2d(child.first,child.second);
if (temp->e<=(r->s+r->e)>>1) r->l=temp;
else r->r=temp;
r->val=temp->val->clone();
}
r->update(i,j,k);
}
val->update(j,max((l==nullptr)?ii(0,-1):l->val->query(j,j),(r==nullptr)?ii(0,-1):r->val->query(j,j)));
}
}
ii query(int i,int j,int i2,int j2){
if (i<=s && e<=j) return val->query(i2,j2);
else if (j<=m) return (l==nullptr)?ii(0,-1):l->query(i,j,i2,j2);
else if (m<i) return (r==nullptr)?ii(0,-1):r->query(i,j,i2,j2);
else return max((l==nullptr)?ii(0,-1):l->query(i,m,i2,j2),(r==nullptr)?ii(0,-1):r->query(m+1,j,i2,j2));
}
};
bool comp(const iii &a, const iii &b) {
if (a.first.second != b.first.second) return a.first.second < b.first.second;
return a < b;
}
int main() {
int N;
scanf("%d", &N);
iii xy[N];
ii pos[N];
minnode2d *minx = new minnode2d(1, 100000), *miny = new minnode2d(1, 100000);
maxnode2d *maxx = new maxnode2d(1, 100000), *maxy = new maxnode2d(1, 100000);
for (int i = 0; i < N; ++i) scanf("%d %d", &pos[i].first, &pos[i].second), xy[i].first = pos[i], xy[i].second = i;
sort(xy, xy + N);
int xf[N], yf[N];
xf[xy[0].second] = -1;
for (int i = 1; i < N; ++i) {
if (xy[i - 1].first.first == xy[i].first.first) xf[xy[i - 1].second] = xy[i].second, xf[xy[i].second] = xy[i - 1].second;
else xf[xy[i].second] = -1;
}
sort(xy, xy + N, comp);
yf[xy[0].second] = -1;
for (int i = 1; i < N; ++i) {
if (xy[i - 1].first.second == xy[i].first.second) yf[xy[i - 1].second] = xy[i].second, yf[xy[i].second] = xy[i - 1].second;
else yf[xy[i].second] = -1;
}
queue<int> despo;
for (int i = 0; i < N; ++i) {
if (xf[i] == -1 && yf[i] == -1) {
printf("NE");
return 0;
} else if (xf[i] == -1 || yf[i] == -1) despo.push(i);
if (xf[i] != -1) minx -> update(pos[i].first, pos[i].second, ii(pos[xf[i]].second, i)), maxx -> update(pos[i].first, pos[i].second, ii(pos[xf[i]].second, i));
if (yf[i] != -1) miny -> update(pos[i].first, pos[i].second, ii(pos[yf[i]].first, i)), maxy -> update(pos[i].first, pos[i].second, ii(pos[yf[i]].first, i));
}
vector<ii> pairs;
bool settled[N];
fill_n(settled, N, false);
while (!despo.empty()) {
int pt1 = despo.front(), pt2;
despo.pop();
if (settled[pt1]) continue;
if (xf[pt1] != -1) {
pt2 = xf[pt1];
minx -> update(pos[pt1].first, pos[pt1].second, ii(INF, -1)), maxx -> update(pos[pt1].first, pos[pt1].second, ii(0, -1));
minx -> update(pos[pt2].first, pos[pt2].second, ii(INF, -1)), maxx -> update(pos[pt2].first, pos[pt2].second, ii(0, -1));
if (yf[pt2] != -1) {
miny -> update(pos[pt2].first, pos[pt2].second, ii(INF, -1)), maxy -> update(pos[pt2].first, pos[pt2].second, ii(0, -1));
miny -> update(pos[yf[pt2]].first, pos[yf[pt2]].second, ii(INF, -1)), maxy -> update(pos[yf[pt2]].first, pos[yf[pt2]].second, ii(0, -1));
yf[yf[pt2]] = -1;
if (xf[yf[pt2]] == -1) {
printf("NE");
return 0;
} else despo.push(yf[pt2]);
}
ii qans = maxy -> query(1, pos[pt1].first - 1, min(pos[pt1].second, pos[pt2].second), max(pos[pt1].second, pos[pt2].second));
while (qans.first > pos[pt1].first) {
miny -> update(pos[qans.second].first, pos[qans.second].second, ii(INF, -1)), maxy -> update(pos[qans.second].first, pos[qans.second].second, ii(0, -1));
yf[qans.second] = -1;
if (xf[qans.second] == -1) {
printf("NE");
return 0;
} else despo.push(qans.second);
qans = maxy -> query(1, pos[pt1].first - 1, min(pos[pt1].second, pos[pt2].second), max(pos[pt1].second, pos[pt2].second));
}
qans = miny -> query(pos[pt1].first + 1, 100000, min(pos[pt1].second, pos[pt2].second), max(pos[pt1].second, pos[pt2].second));
while (qans.first < pos[pt1].first) {
miny -> update(pos[qans.second].first, pos[qans.second].second, ii(INF, -1)), maxy -> update(pos[qans.second].first, pos[qans.second].second, ii(0, -1));
yf[qans.second] = -1;
if (xf[qans.second] == -1) {
printf("NE");
return 0;
} else despo.push(qans.second);
qans = miny -> query(pos[pt1].first + 1, 100000, min(pos[pt1].second, pos[pt2].second), max(pos[pt1].second, pos[pt2].second));
}
} else {
pt2 = yf[pt1];
miny -> update(pos[pt1].first, pos[pt1].second, ii(INF, -1)), maxy -> update(pos[pt1].first, pos[pt1].second, ii(0, -1));
miny -> update(pos[pt2].first, pos[pt2].second, ii(INF, -1)), maxy -> update(pos[pt2].first, pos[pt2].second, ii(0, -1));
if (xf[pt2] != -1) {
minx -> update(pos[pt2].first, pos[pt2].second, ii(INF, -1)), maxx -> update(pos[pt2].first, pos[pt2].second, ii(0, -1));
minx -> update(pos[xf[pt2]].first, pos[xf[pt2]].second, ii(INF, -1)), maxx -> update(pos[xf[pt2]].first, pos[xf[pt2]].second, ii(0, -1));
xf[xf[pt2]] = -1;
if (yf[xf[pt2]] == -1) {
printf("NE");
return 0;
} else despo.push(xf[pt2]);
}
ii qans = maxx -> query(min(pos[pt1].first, pos[pt2].first), max(pos[pt1].first, pos[pt2].first), 1, pos[pt1].second - 1);
while (qans.first > pos[pt1].second) {
minx -> update(pos[qans.second].first, pos[qans.second].second, ii(INF, -1)), maxx -> update(pos[qans.second].first, pos[qans.second].second, ii(0, -1));
xf[qans.second] = -1;
if (yf[qans.second] == -1) {
printf("NE");
return 0;
} else despo.push(qans.second);
qans = maxx -> query(min(pos[pt1].first, pos[pt2].first), max(pos[pt1].first, pos[pt2].first), 1, pos[pt1].second - 1);
}
qans = minx -> query(min(pos[pt1].first, pos[pt2].first), max(pos[pt1].first, pos[pt2].first), pos[pt1].second + 1, 100000);
while (qans.first < pos[pt1].second) {
minx -> update(pos[qans.second].first, pos[qans.second].second, ii(INF, -1)), maxx -> update(pos[qans.second].first, pos[qans.second].second, ii(0, -1));
xf[qans.second] = -1;
if (yf[qans.second] == -1) {
printf("NE");
return 0;
} else despo.push(qans.second);
qans = minx -> query(min(pos[pt1].first, pos[pt2].first), max(pos[pt1].first, pos[pt2].first), pos[pt1].second + 1, 100000);
}
}
pairs.push_back(ii(pt1, pt2));
settled[pt1] = settled[pt2] = true;
}
for (int i = 0; i < N; ++i) {
if (!settled[i]) pairs.push_back(ii(i, xf[i])), settled[i] = settled[xf[i]] = true;
}
printf("DA\n");
for (ii i: pairs) printf("%d %d\n", i.first + 1, i.second + 1);
}
Compilation message
matching.cpp: In function 'int main()':
matching.cpp:219:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
~~~~~^~~~~~~~~~
matching.cpp:224:97: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for (int i = 0; i < N; ++i) scanf("%d %d", &pos[i].first, &pos[i].second), xy[i].first = pos[i], xy[i].second = i;
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
matching.cpp:248:7: warning: argument 1 range [18446744071562067968, 18446744073709551615] exceeds maximum object size 9223372036854775807 [-Walloc-size-larger-than=]
bool settled[N];
^~~~~~~
matching.cpp:248:7: note: in a call to built-in allocation function 'void* __builtin_alloca_with_align(long unsigned int, long unsigned int)'
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| 3 |
Correct |
5 ms |
384 KB |
Output is correct |
| 4 |
Correct |
5 ms |
384 KB |
Output is correct |
| 5 |
Correct |
4 ms |
384 KB |
Output is correct |
| 6 |
Correct |
5 ms |
384 KB |
Output is correct |
| 7 |
Correct |
4 ms |
256 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| 3 |
Correct |
5 ms |
384 KB |
Output is correct |
| 4 |
Correct |
5 ms |
384 KB |
Output is correct |
| 5 |
Correct |
4 ms |
384 KB |
Output is correct |
| 6 |
Correct |
5 ms |
384 KB |
Output is correct |
| 7 |
Correct |
4 ms |
256 KB |
Output is correct |
| 8 |
Correct |
5 ms |
384 KB |
Output is correct |
| 9 |
Correct |
5 ms |
384 KB |
Output is correct |
| 10 |
Correct |
5 ms |
384 KB |
Output is correct |
| 11 |
Correct |
5 ms |
384 KB |
Output is correct |
| 12 |
Correct |
5 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| 3 |
Correct |
5 ms |
384 KB |
Output is correct |
| 4 |
Correct |
5 ms |
384 KB |
Output is correct |
| 5 |
Correct |
4 ms |
384 KB |
Output is correct |
| 6 |
Correct |
5 ms |
384 KB |
Output is correct |
| 7 |
Correct |
4 ms |
256 KB |
Output is correct |
| 8 |
Correct |
5 ms |
384 KB |
Output is correct |
| 9 |
Correct |
5 ms |
384 KB |
Output is correct |
| 10 |
Correct |
5 ms |
384 KB |
Output is correct |
| 11 |
Correct |
5 ms |
384 KB |
Output is correct |
| 12 |
Correct |
5 ms |
384 KB |
Output is correct |
| 13 |
Correct |
39 ms |
6444 KB |
Output is correct |
| 14 |
Correct |
40 ms |
6520 KB |
Output is correct |
| 15 |
Correct |
44 ms |
6520 KB |
Output is correct |
| 16 |
Correct |
40 ms |
6392 KB |
Output is correct |
| 17 |
Correct |
41 ms |
6392 KB |
Output is correct |
| 18 |
Correct |
37 ms |
6520 KB |
Output is correct |
| 19 |
Correct |
39 ms |
6520 KB |
Output is correct |
| 20 |
Correct |
35 ms |
6392 KB |
Output is correct |
| 21 |
Correct |
34 ms |
6392 KB |
Output is correct |
| 22 |
Correct |
34 ms |
6400 KB |
Output is correct |
| 23 |
Correct |
64 ms |
7800 KB |
Output is correct |
| 24 |
Correct |
66 ms |
7800 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| 3 |
Correct |
5 ms |
384 KB |
Output is correct |
| 4 |
Correct |
5 ms |
384 KB |
Output is correct |
| 5 |
Correct |
4 ms |
384 KB |
Output is correct |
| 6 |
Correct |
5 ms |
384 KB |
Output is correct |
| 7 |
Correct |
4 ms |
256 KB |
Output is correct |
| 8 |
Correct |
5 ms |
384 KB |
Output is correct |
| 9 |
Correct |
5 ms |
384 KB |
Output is correct |
| 10 |
Correct |
5 ms |
384 KB |
Output is correct |
| 11 |
Correct |
5 ms |
384 KB |
Output is correct |
| 12 |
Correct |
5 ms |
384 KB |
Output is correct |
| 13 |
Correct |
39 ms |
6444 KB |
Output is correct |
| 14 |
Correct |
40 ms |
6520 KB |
Output is correct |
| 15 |
Correct |
44 ms |
6520 KB |
Output is correct |
| 16 |
Correct |
40 ms |
6392 KB |
Output is correct |
| 17 |
Correct |
41 ms |
6392 KB |
Output is correct |
| 18 |
Correct |
37 ms |
6520 KB |
Output is correct |
| 19 |
Correct |
39 ms |
6520 KB |
Output is correct |
| 20 |
Correct |
35 ms |
6392 KB |
Output is correct |
| 21 |
Correct |
34 ms |
6392 KB |
Output is correct |
| 22 |
Correct |
34 ms |
6400 KB |
Output is correct |
| 23 |
Correct |
64 ms |
7800 KB |
Output is correct |
| 24 |
Correct |
66 ms |
7800 KB |
Output is correct |
| 25 |
Execution timed out |
2596 ms |
291000 KB |
Time limit exceeded |
| 26 |
Halted |
0 ms |
0 KB |
- |
