Submission #445152

#	Time	Username	Problem	Language	Result	Execution time	Memory
445152		lohacho	Matching (COCI20_matching)	C++14	110 / 110	999 ms	131240 KiB

matching

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

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