oj.uz

Submission #218783

# Submission time Handle Problem Language Result Execution time Memory
218783 2020-04-02T18:04:01 Z Vimmer Matching (COCI20_matching) C++14
11 / 110
 61 ms 85760 KB 
#include <bits/stdc++.h>

//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("fast-math")
//#pragma GCC optimize("no-stack-protector")

#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], b[N][2], n, xr[N], yr[N];

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

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

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

vector <pair <int, int> > psh_dely[N * 4];

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

vector <pair <int, int> > g;

void Pushx(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);}
    }
}
void Pushy(int v, int tl, int tr)
{
    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);}
    }

}

void upd(int v, int tl, int tr, int l, int r, int val, bool f)
{
    if (r < tl || tr < l) return;

    if (l <= tl && tr <= r) {if (!f) pshx[v].pb(val); else pshy[v].pb(val); 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);
}

void Push_dely(int v, int tl, int tr)
{
    while (sz(psh_dely[v]) > 0)
    {
        pair <int, int>  pt = psh_dely[v].back();

        psh_dely[v].pop_back();

        ty_del[v].insert(pt);

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

void upd_del(int v, int tl, int tr, int l, int r, pair <int, int> val)
{
    if (tl > tr || l > r || r < tl || tr < l) return;

    if (l <= tl && tr <= r) {psh_dely[v].pb(val); return;}

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

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

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

bool good(int v, int tl, int tr, int pos, int l, int r, bool f)
{
    if (f) Pushy(v, tl, tr); else Pushx(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);
    }
}
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);
    }
}
void add_remove(int fr, int sc, int nm)
{
    if (!mk[fr]) {if ((a[fr][1] == a[fr][0] && a[fr][0] == -1) || (a[fr][1] != -1 && !gd(fr, a[fr][1])) || (a[fr][0] != -1 && !gd(fr, a[fr][0])) ){cout << "NE" << endl; exit(0);} alone.insert(fr);}

    if (!mk[sc]) {if ((a[sc][1] == a[sc][0] && a[sc][0] == -1) || (a[sc][1] != -1 && !gd(sc, a[sc][1])) || (a[sc][0] != -1 && !gd(sc, a[sc][0])) ){cout << "NE" << endl; exit(0);} alone.insert(sc);}
}

void good_del(int v, int tl, int tr, int pos, int l, int r)
{
    Push_dely(v, tl, tr);

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

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

        while (it != ty_del[v].end() && (*it).F <= r) {add_remove(b[(*it).S][0], (*it).S, (*it).S); it++;}
    }
    else
    {
        int md = (tl + tr) >> 1;

        if (pos <= md) good_del(v + v, tl, md, pos, l, r);
          else  good_del(v + v + 1, md + 1, tr, pos, l, r);
    }
}

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

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

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);
    }
    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);
    }
}

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

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

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


void fnd()
{
    while (sz(alone) > 0)
    {
        int v = *alone.begin();

        alone.erase(alone.begin());

        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 (int i = 0; i < n; i++)
    {
        if (mk[i]) continue;

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

        clr(a[i][0]);

        clr(i);
    }
}

void add_del(int fr, int 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], fr });
}
int main()
{
    ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n;

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

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

    for (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 (int i = 0; i < n; i++)
    {
        b[i][0] = a[i][0];

        b[i][1] = a[i][1];

        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.insert(i); else add_del(i, a[i][0]);
    }

    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;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 85632 KB Output is correct
2 Correct 53 ms 85628 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 85632 KB Output is correct
2 Correct 53 ms 85628 KB Output is correct
3 Correct 58 ms 85752 KB Output is correct
4 Correct 56 ms 85624 KB Output is correct
5 Correct 58 ms 85756 KB Output is correct
6 Correct 54 ms 85760 KB Output is correct
7 Correct 59 ms 85624 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 85632 KB Output is correct
2 Correct 53 ms 85628 KB Output is correct
3 Correct 58 ms 85752 KB Output is correct
4 Correct 56 ms 85624 KB Output is correct
5 Correct 58 ms 85756 KB Output is correct
6 Correct 54 ms 85760 KB Output is correct
7 Correct 59 ms 85624 KB Output is correct
8 Correct 61 ms 85752 KB Output is correct
9 Incorrect 54 ms 85632 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 85632 KB Output is correct
2 Correct 53 ms 85628 KB Output is correct
3 Correct 58 ms 85752 KB Output is correct
4 Correct 56 ms 85624 KB Output is correct
5 Correct 58 ms 85756 KB Output is correct
6 Correct 54 ms 85760 KB Output is correct
7 Correct 59 ms 85624 KB Output is correct
8 Correct 61 ms 85752 KB Output is correct
9 Incorrect 54 ms 85632 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 85632 KB Output is correct
2 Correct 53 ms 85628 KB Output is correct
3 Correct 58 ms 85752 KB Output is correct
4 Correct 56 ms 85624 KB Output is correct
5 Correct 58 ms 85756 KB Output is correct
6 Correct 54 ms 85760 KB Output is correct
7 Correct 59 ms 85624 KB Output is correct
8 Correct 61 ms 85752 KB Output is correct
9 Incorrect 54 ms 85632 KB Output isn't correct
10 Halted 0 ms 0 KB -