Submission #217239

#	Time	Username	Problem	Language	Result	Execution time	Memory
217239		VEGAnn	Matching (COCI20_matching)	C++14	110 / 110	519 ms	132208 KiB

matching

#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define pii pair<int,int>
#define pi3 pair<pii,int>
#define ft first
#define sd second
#define all(x) x.begin(),x.end()
#define PB push_back
#define MP make_pair
#define MP3(a,b,c) MP(MP(a,b),c)
using namespace std;
typedef long long ll;
const int md = int(1e9) + 7;
const int N = 100100;
const int PW = 20;
const int oo = 2e9;
set<pii> ste;
vector<pii> res;
vector<pi3> vec[2];
vector<int> vc, vx[N], vy[N];
int n, x[N], y[N], sosed_x[N], sosed_y[N], kol[N];
bool mrk[N], fd = 0;
pii loc;

void BAD(){
    cout << "NE";
    exit(0);
}

struct seg_tree{
    vector<pii> vec;
    vector<pii> tree;

    seg_tree(): vec(0), tree(0) {}

    void build(int v, int l, int r){
        if (l == r) {
            tree[v] = MP(vec[l].sd, vec[l].ft);
            return;
        }
        int md = (l + r) >> 1;

        build(v + v, l, md);
        build(v + v + 1, md + 1, r);

        tree[v] = max(tree[v + v], tree[v + v + 1]);
    }

    pii get(int v, int l, int r, int lht, int rht){
        if (lht > vec[r].ft || rht < vec[l].ft) return MP(-oo, -oo);

        if (vec[l].ft >= lht && vec[r].ft <= rht)
            return tree[v];

        int md = (l + r) >> 1;

        return max(get(v + v, l, md, lht, rht),
                   get(v + v + 1, md + 1, r, lht, rht));
    }

    void update(int v, int l, int r, pii cur){
        if (l == r){
            tree[v] = MP(-oo, -oo);
            return;
        }

        int md = (l + r) >> 1;

        if (cur <= vec[md])
            update(v + v, l, md, cur);
        else update(v + v + 1, md + 1, r, cur);

        tree[v] = max(tree[v + v], tree[v + v + 1]);
    }
};

seg_tree st[2][4 * N];

void build(int tp, int v, int l, int r){
    if (l == r){
        st[tp][v].vec.clear();
        st[tp][v].vec.PB(MP(vec[tp][l].sd, vec[tp][l].ft.sd));
        st[tp][v].tree.resize(2);
        st[tp][v].tree[1] = MP(vec[tp][l].ft.sd, vec[tp][l].sd);
        return;
    }

    int md = (l + r) >> 1;
    build(tp, v + v, l, md);
    build(tp, v + v + 1, md + 1, r);

    merge(all(st[tp][v + v].vec), all(st[tp][v + v + 1].vec), back_inserter(st[tp][v].vec));
    st[tp][v].tree.resize(sz(st[tp][v].vec) * 4 + 3);
    st[tp][v].build(1, 0, sz(st[tp][v].vec) - 1);
}

void search(int tp, int v, int l, int r, int lht, int rht, int vl){
    if (fd) return;

    if (vec[tp][l].ft.ft > vl) return;
    if (vec[tp][r].ft.ft <= vl){

        pii mem = st[tp][v].get(1, 0, sz(st[tp][v].vec) - 1, lht, rht);

        if (mem.ft >= vl){
            fd = 1;
            loc = mem;
        }
        return;
    }

    int md = (l + r) >> 1;
    search(tp, v + v, l, md, lht, rht, vl);
    search(tp, v + v + 1, md + 1, r, lht, rht, vl);
}

void update(int tp, int v, int l, int r, pi3 cur){
    st[tp][v].update(1, 0, sz(st[tp][v].vec) - 1, MP(cur.sd, cur.ft.sd));

    if (l == r) return;

    int md = (l + r) >> 1;

    if (cur <= vec[tp][md])
        update(tp, v + v, l, md, cur);
    else update(tp, v + v + 1, md + 1, r, cur);
}

int main(){


    ios_base::sync_with_stdio(0); cin.tie(0);

//    freopen("in.txt","r",stdin);

    cin >> n;
    vc.clear();

    for (int i = 0; i < n; i++) {
        cin >> x[i] >> y[i];
        vc.PB(x[i]);

        sosed_x[i] = sosed_y[i] = -1;
    }

    sort(all(vc));
    vc.resize(unique(all(vc)) - vc.begin());

    for (int i = 0; i < n; i++)
        x[i] = lower_bound(all(vc), x[i]) - vc.begin();

    vc.clear();
    for (int i = 0; i < n; i++)
        vc.PB(y[i]);

    sort(all(vc));
    vc.resize(unique(all(vc)) - vc.begin());

    for (int i = 0; i < n; i++)
        y[i] = lower_bound(all(vc), y[i]) - vc.begin();

    for (int i = 0; i < n; i++){
        vx[x[i]].PB(i);
        vy[y[i]].PB(i);
    }

    for (int i = 0; i < n; i++){
        if (sz(vx[i]) == 2){
            sosed_x[vx[i][0]] = vx[i][1];
            sosed_x[vx[i][1]] = vx[i][0];
            kol[vx[i][0]]++;
            kol[vx[i][1]]++;

            int lf = min(y[vx[i][0]], y[vx[i][1]]);
            int rt = max(y[vx[i][0]], y[vx[i][1]]);

            vec[0].PB(MP3(lf, rt, i));
        }

        if (sz(vy[i]) == 2){
            sosed_y[vy[i][0]] = vy[i][1];
            sosed_y[vy[i][1]] = vy[i][0];
            kol[vy[i][0]]++;
            kol[vy[i][1]]++;

            int lf = min(x[vy[i][0]], x[vy[i][1]]);
            int rt = max(x[vy[i][0]], x[vy[i][1]]);

            vec[1].PB(MP3(lf, rt, i));
        }
    }

    for (int i = 0; i < n; i++)
        ste.insert(MP(kol[i], i));

    for (int tp = 0; tp < 2; tp++){
        if (!sz(vec[tp])) continue;

        sort(all(vec[tp]));
        build(tp, 1, 0, sz(vec[tp]) - 1);
    }

    while (sz(ste)){
        int v = (*ste.begin()).sd;
        ste.erase(ste.begin());
        mrk[v] = 1;

        if (kol[v] == 0)
            BAD();

        if (kol[v] == 2){
            for (int i = 0; i < n; i++)
                if (!mrk[i]){
                    mrk[i] = 1;
                    mrk[sosed_x[i]] = 1;

                    res.PB(MP(i, sosed_x[i]));
                }

            break;
        }

        if (sosed_x[v] >= 0){
            int u = sosed_x[v];
            mrk[u] = 1;
            res.PB(MP(u, v));
            ste.erase(MP(kol[u], u));
            int rbd = max(y[u], y[v]);
            int lbd = min(y[u], y[v]);

            while (1){
                fd = 0;
                if (!sz(vec[1])) break;

                search(1, 1, 0, sz(vec[1]) - 1, lbd, rbd, x[v]);

                if (!fd) break;

                int lf = loc.sd;

                int n1 = vy[lf][0], n2 = vy[lf][1];
                int le = min(x[n1], x[n2]);
                int ri = max(x[n1], x[n2]);

                if (le <= x[v] && ri >= x[v]){
                    ste.erase(MP(kol[n1], n1));
                    ste.erase(MP(kol[n2], n2));
                    kol[n1]--;
                    kol[n2]--;
                    if (!mrk[n1]) ste.insert(MP(kol[n1], n1));
                    if (!mrk[n2]) ste.insert(MP(kol[n2], n2));
                    vy[lf].clear();
                    sosed_y[n1] = -1;
                    sosed_y[n2] = -1;
                }

                update(1, 1, 0, sz(vec[1]) - 1, MP3(le, ri, loc.sd));
            }
        } else {
            int u = sosed_y[v];
            mrk[u] = 1;
            res.PB(MP(u, v));
            ste.erase(MP(kol[u], u));

            int rbd = max(x[u], x[v]);
            int lbd = min(x[u], x[v]);

            while (1){
                fd = 0;
                if (!sz(vec[0])) break;
                search(0, 1, 0, sz(vec[0]) - 1, lbd, rbd, y[v]);

                if (!fd) break;

                int lf = loc.sd;

                int n1 = vx[lf][0], n2 = vx[lf][1];
                int le = min(y[n1], y[n2]);
                int ri = max(y[n1], y[n2]);

                if (le <= y[v] && ri >= y[v]){
                    ste.erase(MP(kol[n1], n1));
                    ste.erase(MP(kol[n2], n2));
                    kol[n1]--;
                    kol[n2]--;
                    if (!mrk[n1]) ste.insert(MP(kol[n1], n1));
                    if (!mrk[n2]) ste.insert(MP(kol[n2], n2));
                    vx[lf].clear();
                    sosed_x[n1] = -1;
                    sosed_x[n2] = -1;
                }

                update(0, 1, 0, sz(vec[0]) - 1, MP3(le, ri, loc.sd));
            }
        }
    }

    cout << "DA\n";
    for (pii cr : res)
        cout << cr.ft + 1 << " " << cr.sd + 1 << '\n';

    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 40 / 40
• Subtask 5: 52 / 52