Submission #218709

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
218709	2020-04-02T14:45:56 Z	Vimmer	Matching (COCI20_matching)	C++14	Compilation error	0 ms	0 KB

matching

#include <bits/stdc++.h>

//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")

#define F first
#define S second
#define sz(x) int(x.size())
#define pb push_back
#define N 100001

using namespace std;

int x[N], y[N], a[N][2], n, xr[N], yr[N];

set <int> tx[N * 4], ty[N * 4];

set <pair <int, int> > tx_del[N * 4], ty_del[N * 4];

vector <int> pshx[N * 4], pshy[N * 4];

vector <pair <int, int> > pshx_del[N * 4], pshy_del[N * 4], pshx_add[N * 4], pshy_add[N * 4];

bool mk[N], mkr[N][2];

queue <int> alone;

vector <pair <int, int> > g, gr;

inline void Push(int &v, int &tl, int &tr)
{
    while (sz(pshx[v]) > 0)
    {
        int val = pshx[v].back();

        pshx[v].pop_back();

        tx[v].insert(val);

        if (tl != tr) {pshx[v + v].pb(val); pshx[v + v + 1].pb(val);}
    }

    while (sz(pshy[v]) > 0)
    {
        int val = pshy[v].back();

        pshy[v].pop_back();

        ty[v].insert(val);

        if (tl != tr) {pshy[v + v].pb(val); pshy[v + v + 1].pb(val);}
    }
}
inline void upd(int &v, int &tl, int &tr, int &l, int &r, int &val, bool &f)
{
    Push(v, tl, tr);

    if (tl > tr || l > r || r < tl || tr < l) return;

    if (l <= tl && tr <= r) {if (!f) pshx[v].pb(val); else pshy[v].pb(val); Push(v, tl, tr); return;}

    int md = (tl + tr) >> 1;

    upd(v + v, tl, md, l, r, val, f);

    upd(v + v + 1, md + 1, tr, l, r, val, f);
}

inline void Push_del(int &v, int &tl, int &tr)
{
    while (sz(pshx_add[v]) > 0)
    {
        pair <int, int>  pt = pshx_add[v].back();

        pshx_add[v].pop_back();

        tx_del[v].insert(pt);

        if (tl != tr) {pshx_add[v + v].pb(pt); pshx_add[v + v + 1].pb(pt); }
    }

    while (sz(pshy_add[v]) > 0)
    {
        pair <int, int> pt = pshy_add[v].back();

        pshy_add[v].pop_back();

        ty_del[v].insert(pt);

        if (tl != tr) {pshy_add[v + v].pb(pt); pshy_add[v + v + 1].pb(pt); }
    }

    while (sz(pshx_del[v]) > 0)
    {
        pair <int, int> pt = pshx_del[v].back();

        pshx_del[v].pop_back();

        tx_del[v].erase(pt);

        if (tl != tr) {pshx_del[v + v].pb(pt); pshx_del[v + v + 1].pb(pt); }
    }

    while (sz(pshy_del[v]) > 0)
    {
        pair <int, int> pt = pshy_del[v].back();

        pshy_del[v].pop_back();

        ty_del[v].erase(pt);

        if (tl != tr) {pshy_del[v + v].pb(pt); pshy_del[v + v + 1].pb(pt);}
    }
}

inline void upd_del(int &v, int &tl, int &tr, int &l, int &r, pair <int, int> &val, bool &f)
{
    Push_del(v, tl, tr);

    if (tl > tr || l > r || r < tl || tr < l) return;

    if (l <= tl && tr <= r) {if (!f) pshx_add[v].pb(val); else pshy_add[v].pb(val); Push_del(v, tl, tr); return;}

    int md = (tl + tr) >> 1;

    upd_del(v + v, tl, md, l, r, val, f);

    upd_del(v + v + 1, md + 1, tr, l, r, val, f);
}

inline void upd_remove(int &v, int &tl, int &tr, int &l, int &r, pair <int, int> &val, bool &f)
{
    Push_del(v, tl, tr);

    if (tl > tr || l > r || r < tl || tr < l) return;

    if (l <= tl && tr <= r) {if (!f) pshx_del[v].pb(val); else pshy_del[v].pb(val); Push_del(v, tl, tr); return;}

    int md = (tl + tr) >> 1;

    upd_remove(v + v, tl, md, l, r, val, f);

    upd_remove(v + v + 1, md + 1, tr, l, r, val, f);
}

inline bool good(int &v, int &tl, int &tr, int &pos, int &l, int &r, bool &f)
{
    Push(v, tl, tr);

    if (tl == tr)
    {
        set <int> :: iterator it;

        if (f)
        {
            it = ty[v].lower_bound(l);

            return (it == ty[v].end() ? 1 : *it > r);
        }
        else
        {
            it = tx[v].lower_bound(l);

            return (it == tx[v].end() ? 1 : *it > r);
        }
    }
    else
    {
        int md = (tl + tr) >> 1;

        if (pos <= md) return good(v + v, tl, md, pos, l, r, f);

        return good(v + v + 1, md + 1, tr, pos, l, r, f);
    }
}

inline int good_del(int &v, int &tl, int &tr, int &pos, int &l, int &r, bool &f)
{
    Push_del(v, tl, tr);

    if (tl == tr)
    {
        set <pair <int, int> > :: iterator it;

        if (f)
        {
            it = ty_del[v].lower_bound({l, -1e9});

            if (it == ty_del[v].end() || (*it).F > r) return -1;

            return (*it).S;
        }
        else
        {
            it = tx_del[v].lower_bound({l, -1e9});

            if (it == tx_del[v].end() || (*it).F > r) return -1;

            return (*it).S;
        }
    }
    else
    {
        int md = (tl + tr) >> 1;

        if (pos <= md) return good_del(v + v, tl, md, pos, l, r, f);

        return good_del(v + v + 1, md + 1, tr, pos, l, r, f);
    }
}

inline bool gd(int &fr, int &sc)
{
    if (x[fr] == x[sc])
    {
        if (y[fr] > y[sc]) swap(fr, sc);

        return good(1, 1, N - 1, x[fr], y[fr], y[sc], 0);
    }
    else
    {
        if (x[fr] > x[sc]) swap(fr, sc);

        return good(1, 1, N - 1, y[fr], x[fr], x[sc], 1);
    }
}

inline void add_remove(int &fr, int &sc, int &nm)
{
    if (!mk[fr]) alone.push(fr);

    if (!mk[sc]) alone.push(sc);

    if (x[fr] == x[sc])
    {
        if (y[fr] > y[sc]) swap(fr, sc);

        upd_remove(1, 1, N, y[fr], y[sc], {x[fr], nm }, 1);
    }
    else
    {
        if (x[fr] > x[sc]) swap(fr, sc);

        upd_remove(1, 1, N, x[fr], x[sc], {y[fr], nm }, 0);
    }
}

inline void seacrh(int &fr, int &sc)
{
    if (x[fr] == x[sc])
    {
        if (y[fr] > y[sc]) swap(fr, sc);

        int pt = good_del(1, 1, N, x[fr], y[fr], y[sc], 0);

        while (pt != -1)
        {
            add_remove(gr[pt].F, gr[pt].S, pt);

            pt = good_del(1, 1, N, x[fr], y[fr], y[sc], 0);
        }
    }
    else
    {
        if (x[fr] > x[sc]) swap(fr, sc);

        int pt = good_del(1, 1, N, y[fr], x[fr], x[sc], 1);

        while (pt != -1)
        {
            add_remove(gr[pt].F, gr[pt].S, pt);

            pt = good_del(1, 1, N, y[fr], x[fr], x[sc], 1);
        }
    }
}

inline void add(int &fr, int &sc)
{
    if (x[fr] == x[sc])
    {
        g.pb({fr, sc});

        if (y[fr] > y[sc]) swap(fr, sc);

        upd(1, 1, N - 1, y[fr], y[sc], x[fr], 1);

        seacrh(fr, sc);
    }
    else
    {
        g.pb({fr, sc});

        if (x[fr] > x[sc]) swap(fr, sc);

        upd(1, 1, N - 1, x[fr], x[sc], y[fr], 0);

        seacrh(fr, sc);
    }
}

inline void clr(int &x)
{
    mk[x] = 1;

    if (a[x][1] != -1) {if (!mk[a[x][1]]) alone.push(a[x][1]); a[x][1] = a[a[x][1]][1] = -1;}

    if (a[x][0] != -1) {if (!mk[a[x][0]]) alone.push(a[x][0]); a[x][0] = a[a[x][0]][0] = -1;}
}


inline void fnd()
{
    while (sz(alone) > 0)
    {
        int v = alone.front();

        alone.pop();

        if (mk[v]) continue;

        if (a[v][1] != -1 && gd(v, a[v][1])) {add(v, a[v][1]); clr(a[v][1]); clr(v); continue;}

        if (a[v][0] != -1 && gd(v, a[v][0])) {add(v, a[v][0]); clr(a[v][0]); clr(v); continue;}

        cout << "NE" << endl;

        exit(0);
    }

    for (register int i = 0; i < n; i++)
    {
        if (mk[i]) continue;

        g.pb({i, a[i][0]});

        clr(a[i][0]);

        clr(i);
    }
}

inline void add_del(int &fr, int &sc)
{
    if (x[fr] == x[sc])
    {
        if (mkr[fr][0]) return;

        mkr[fr][0] = 1;

        mkr[sc][0] = 1;

        if (y[fr] > y[sc]) swap(fr, sc);

        upd_del(1, 1, N, y[fr], y[sc], {x[fr], sz(gr) }, 1);

        gr.pb({fr, sc});
    }
    else
    {
        if (mkr[fr][1]) return;

        mkr[fr][1] = 1;

        mkr[sc][1] = 1;

        if (x[fr] > x[sc]) swap(fr, sc);

        upd_del(1, 1, N, x[fr], x[sc], {y[fr], sz(gr) }, 0);

        gr.pb({fr, sc});
    }
}
int main()
{
    ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n;

    for (register int i = 1; i < N; i++) xr[i] = yr[i] = -1;

    for (register int i = 0; i < n; i++) {cin >> x[i] >> y[i]; a[i][0] = a[i][1] = -1;}

    for (register int i = 0; i < n; i++)
        {
            int X = x[i], Y = y[i];

            if (xr[X] == -1) xr[X] = i; else {a[i][0] = xr[X]; a[xr[X]][0] = i;}

            if (yr[Y] == -1) yr[Y] = i; else {a[i][1] = yr[Y]; a[yr[Y]][1] = i;}
        }

    for (register int i = 0; i < n; i++)
    {
        if (a[i][0] == a[i][1] && a[i][1] == -1) {cout << "NE" << endl; exit(0);}

        if (a[i][0] == -1 || a[i][1] == -1) alone.push(i); else {add_del(i, a[i][0]); add_del(i, a[i][1]);}
    }

    fnd();

    if (sz(g) != n / 2) {cout << "NE" << endl; exit(0);}

    cout << "DA" << endl;

    for (auto it : g) cout << it.F + 1 << " " << it.S + 1 << endl;
}

Compilation message

matching.cpp: In function 'void upd(int&, int&, int&, int&, int&, int&, bool&)':
matching.cpp:65:11: error: cannot bind non-const lvalue reference of type 'int&' to an rvalue of type 'int'
     upd(v + v, tl, md, l, r, val, f);
         ~~^~~
matching.cpp:55:13: note:   initializing argument 1 of 'void upd(int&, int&, int&, int&, int&, int&, bool&)'
 inline void upd(int &v, int &tl, int &tr, int &l, int &r, int &val, bool &f)
             ^~~
matching.cpp:67:15: error: cannot bind non-const lvalue reference of type 'int&' to an rvalue of type 'int'
     upd(v + v + 1, md + 1, tr, l, r, val, f);
         ~~~~~~^~~
matching.cpp:55:13: note:   initializing argument 1 of 'void upd(int&, int&, int&, int&, int&, int&, bool&)'
 inline void upd(int &v, int &tl, int &tr, int &l, int &r, int &val, bool &f)
             ^~~
matching.cpp: In function 'void upd_del(int&, int&, int&, int&, int&, std::pair<int, int>&, bool&)':
matching.cpp:127:15: error: cannot bind non-const lvalue reference of type 'int&' to an rvalue of type 'int'
     upd_del(v + v, tl, md, l, r, val, f);
             ~~^~~
matching.cpp:117:13: note:   initializing argument 1 of 'void upd_del(int&, int&, int&, int&, int&, std::pair<int, int>&, bool&)'
 inline void upd_del(int &v, int &tl, int &tr, int &l, int &r, pair <int, int> &val, bool &f)
             ^~~~~~~
matching.cpp:129:19: error: cannot bind non-const lvalue reference of type 'int&' to an rvalue of type 'int'
     upd_del(v + v + 1, md + 1, tr, l, r, val, f);
             ~~~~~~^~~
matching.cpp:117:13: note:   initializing argument 1 of 'void upd_del(int&, int&, int&, int&, int&, std::pair<int, int>&, bool&)'
 inline void upd_del(int &v, int &tl, int &tr, int &l, int &r, pair <int, int> &val, bool &f)
             ^~~~~~~
matching.cpp: In function 'void upd_remove(int&, int&, int&, int&, int&, std::pair<int, int>&, bool&)':
matching.cpp:142:18: error: cannot bind non-const lvalue reference of type 'int&' to an rvalue of type 'int'
     upd_remove(v + v, tl, md, l, r, val, f);
                ~~^~~
matching.cpp:132:13: note:   initializing argument 1 of 'void upd_remove(int&, int&, int&, int&, int&, std::pair<int, int>&, bool&)'
 inline void upd_remove(int &v, int &tl, int &tr, int &l, int &r, pair <int, int> &val, bool &f)
             ^~~~~~~~~~
matching.cpp:144:22: error: cannot bind non-const lvalue reference of type 'int&' to an rvalue of type 'int'
     upd_remove(v + v + 1, md + 1, tr, l, r, val, f);
                ~~~~~~^~~
matching.cpp:132:13: note:   initializing argument 1 of 'void upd_remove(int&, int&, int&, int&, int&, std::pair<int, int>&, bool&)'
 inline void upd_remove(int &v, int &tl, int &tr, int &l, int &r, pair <int, int> &val, bool &f)
             ^~~~~~~~~~
matching.cpp: In function 'bool good(int&, int&, int&, int&, int&, int&, bool&)':
matching.cpp:172:38: error: cannot bind non-const lvalue reference of type 'int&' to an rvalue of type 'int'
         if (pos <= md) return good(v + v, tl, md, pos, l, r, f);
                                    ~~^~~
matching.cpp:147:13: note:   initializing argument 1 of 'bool good(int&, int&, int&, int&, int&, int&, bool&)'
 inline bool good(int &v, int &tl, int &tr, int &pos, int &l, int &r, bool &f)
             ^~~~
matching.cpp:174:27: error: cannot bind non-const lvalue reference of type 'int&' to an rvalue of type 'int'
         return good(v + v + 1, md + 1, tr, pos, l, r, f);
                     ~~~~~~^~~
matching.cpp:147:13: note:   initializing argument 1 of 'bool good(int&, int&, int&, int&, int&, int&, bool&)'
 inline bool good(int &v, int &tl, int &tr, int &pos, int &l, int &r, bool &f)
             ^~~~
matching.cpp: In function 'int good_del(int&, int&, int&, int&, int&, int&, bool&)':
matching.cpp:207:42: error: cannot bind non-const lvalue reference of type 'int&' to an rvalue of type 'int'
         if (pos <= md) return good_del(v + v, tl, md, pos, l, r, f);
                                        ~~^~~
matching.cpp:178:12: note:   initializing argument 1 of 'int good_del(int&, int&, int&, int&, int&, int&, bool&)'
 inline int good_del(int &v, int &tl, int &tr, int &pos, int &l, int &r, bool &f)
            ^~~~~~~~
matching.cpp:209:31: error: cannot bind non-const lvalue reference of type 'int&' to an rvalue of type 'int'
         return good_del(v + v + 1, md + 1, tr, pos, l, r, f);
                         ~~~~~~^~~
matching.cpp:178:12: note:   initializing argument 1 of 'int good_del(int&, int&, int&, int&, int&, int&, bool&)'
 inline int good_del(int &v, int &tl, int &tr, int &pos, int &l, int &r, bool &f)
            ^~~~~~~~
matching.cpp: In function 'bool gd(int&, int&)':
matching.cpp:219:56: error: cannot bind non-const lvalue reference of type 'int&' to an rvalue of type 'int'
         return good(1, 1, N - 1, x[fr], y[fr], y[sc], 0);
                                                        ^
matching.cpp:147:13: note:   initializing argument 1 of 'bool good(int&, int&, int&, int&, int&, int&, bool&)'
 inline bool good(int &v, int &tl, int &tr, int &pos, int &l, int &r, bool &f)
             ^~~~
matching.cpp:225:56: error: cannot bind non-const lvalue reference of type 'int&' to an rvalue of type 'int'
         return good(1, 1, N - 1, y[fr], x[fr], x[sc], 1);
                                                        ^
matching.cpp:147:13: note:   initializing argument 1 of 'bool good(int&, int&, int&, int&, int&, int&, bool&)'
 inline bool good(int &v, int &tl, int &tr, int &pos, int &l, int &r, bool &f)
             ^~~~
matching.cpp: In function 'void add_remove(int&, int&, int&)':
matching.cpp:239:58: error: cannot bind non-const lvalue reference of type 'int&' to an rvalue of type 'int'
         upd_remove(1, 1, N, y[fr], y[sc], {x[fr], nm }, 1);
                                                          ^
matching.cpp:132:13: note:   initializing argument 1 of 'void upd_remove(int&, int&, int&, int&, int&, std::pair<int, int>&, bool&)'
 inline void upd_remove(int &v, int &tl, int &tr, int &l, int &r, pair <int, int> &val, bool &f)
             ^~~~~~~~~~
matching.cpp:245:58: error: cannot bind non-const lvalue reference of type 'int&' to an rvalue of type 'int'
         upd_remove(1, 1, N, x[fr], x[sc], {y[fr], nm }, 0);
                                                          ^
matching.cpp:132:13: note:   initializing argument 1 of 'void upd_remove(int&, int&, int&, int&, int&, std::pair<int, int>&, bool&)'
 inline void upd_remove(int &v, int &tl, int &tr, int &l, int &r, pair <int, int> &val, bool &f)
             ^~~~~~~~~~
matching.cpp: In function 'void seacrh(int&, int&)':
matching.cpp:255:58: error: cannot bind non-const lvalue reference of type 'int&' to an rvalue of type 'int'
         int pt = good_del(1, 1, N, x[fr], y[fr], y[sc], 0);
                                                          ^
matching.cpp:178:12: note:   initializing argument 1 of 'int good_del(int&, int&, int&, int&, int&, int&, bool&)'
 inline int good_del(int &v, int &tl, int &tr, int &pos, int &l, int &r, bool &f)
            ^~~~~~~~
matching.cpp:261:58: error: cannot bind non-const lvalue reference of type 'int&' to an rvalue of type 'int'
             pt = good_del(1, 1, N, x[fr], y[fr], y[sc], 0);
                                                          ^
matching.cpp:178:12: note:   initializing argument 1 of 'int good_del(int&, int&, int&, int&, int&, int&, bool&)'
 inline int good_del(int &v, int &tl, int &tr, int &pos, int &l, int &r, bool &f)
            ^~~~~~~~
matching.cpp:268:58: error: cannot bind non-const lvalue reference of type 'int&' to an rvalue of type 'int'
         int pt = good_del(1, 1, N, y[fr], x[fr], x[sc], 1);
                                                          ^
matching.cpp:178:12: note:   initializing argument 1 of 'int good_del(int&, int&, int&, int&, int&, int&, bool&)'
 inline int good_del(int &v, int &tl, int &tr, int &pos, int &l, int &r, bool &f)
            ^~~~~~~~
matching.cpp:274:58: error: cannot bind non-const lvalue reference of type 'int&' to an rvalue of type 'int'
             pt = good_del(1, 1, N, y[fr], x[fr], x[sc], 1);
                                                          ^
matching.cpp:178:12: note:   initializing argument 1 of 'int good_del(int&, int&, int&, int&, int&, int&, bool&)'
 inline int good_del(int &v, int &tl, int &tr, int &pos, int &l, int &r, bool &f)
            ^~~~~~~~
matching.cpp: In function 'void add(int&, int&)':
matching.cpp:287:48: error: cannot bind non-const lvalue reference of type 'int&' to an rvalue of type 'int'
         upd(1, 1, N - 1, y[fr], y[sc], x[fr], 1);
                                                ^
matching.cpp:55:13: note:   initializing argument 1 of 'void upd(int&, int&, int&, int&, int&, int&, bool&)'
 inline void upd(int &v, int &tl, int &tr, int &l, int &r, int &val, bool &f)
             ^~~
matching.cpp:297:48: error: cannot bind non-const lvalue reference of type 'int&' to an rvalue of type 'int'
         upd(1, 1, N - 1, x[fr], x[sc], y[fr], 0);
                                                ^
matching.cpp:55:13: note:   initializing argument 1 of 'void upd(int&, int&, int&, int&, int&, int&, bool&)'
 inline void upd(int &v, int &tl, int &tr, int &l, int &r, int &val, bool &f)
             ^~~
matching.cpp: In function 'void add_del(int&, int&)':
matching.cpp:356:59: error: cannot bind non-const lvalue reference of type 'int&' to an rvalue of type 'int'
         upd_del(1, 1, N, y[fr], y[sc], {x[fr], sz(gr) }, 1);
                                                           ^
matching.cpp:117:13: note:   initializing argument 1 of 'void upd_del(int&, int&, int&, int&, int&, std::pair<int, int>&, bool&)'
 inline void upd_del(int &v, int &tl, int &tr, int &l, int &r, pair <int, int> &val, bool &f)
             ^~~~~~~
matching.cpp:370:59: error: cannot bind non-const lvalue reference of type 'int&' to an rvalue of type 'int'
         upd_del(1, 1, N, x[fr], x[sc], {y[fr], sz(gr) }, 0);
                                                           ^
matching.cpp:117:13: note:   initializing argument 1 of 'void upd_del(int&, int&, int&, int&, int&, std::pair<int, int>&, bool&)'
 inline void upd_del(int &v, int &tl, int &tr, int &l, int &r, pair <int, int> &val, bool &f)
             ^~~~~~~