oj.uz

Submission #445049

# Submission time Handle Problem Language Result Execution time Memory
445049 2021-07-16T10:13:29 Z lohacho Matching (COCI20_matching) C++14
11 / 110
 29 ms 44220 KB 
#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);
    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];
        for(int rep = 0; rep < 2; ++rep){
            if(a[nx].first != a[ny].first && (int)x[a[nx].first].size() == 2){
                px(a[nx].first, num);
            }
            if(a[nx].second != a[ny].second && (int)y[a[nx].second].size() == 2){
                py(a[nx].second, num);
            }
            swap(nx, ny);
        }
        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;
    }
    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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 44220 KB Output is correct
2 Correct 28 ms 44184 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 44220 KB Output is correct
2 Correct 28 ms 44184 KB Output is correct
3 Correct 28 ms 44100 KB Output is correct
4 Correct 29 ms 44124 KB Output is correct
5 Correct 28 ms 44108 KB Output is correct
6 Correct 24 ms 44048 KB Output is correct
7 Correct 24 ms 44180 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 44220 KB Output is correct
2 Correct 28 ms 44184 KB Output is correct
3 Correct 28 ms 44100 KB Output is correct
4 Correct 29 ms 44124 KB Output is correct
5 Correct 28 ms 44108 KB Output is correct
6 Correct 24 ms 44048 KB Output is correct
7 Correct 24 ms 44180 KB Output is correct
8 Correct 28 ms 44116 KB Output is correct
9 Correct 27 ms 44152 KB Output is correct
10 Correct 27 ms 44108 KB Output is correct
11 Incorrect 29 ms 44132 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 44220 KB Output is correct
2 Correct 28 ms 44184 KB Output is correct
3 Correct 28 ms 44100 KB Output is correct
4 Correct 29 ms 44124 KB Output is correct
5 Correct 28 ms 44108 KB Output is correct
6 Correct 24 ms 44048 KB Output is correct
7 Correct 24 ms 44180 KB Output is correct
8 Correct 28 ms 44116 KB Output is correct
9 Correct 27 ms 44152 KB Output is correct
10 Correct 27 ms 44108 KB Output is correct
11 Incorrect 29 ms 44132 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 44220 KB Output is correct
2 Correct 28 ms 44184 KB Output is correct
3 Correct 28 ms 44100 KB Output is correct
4 Correct 29 ms 44124 KB Output is correct
5 Correct 28 ms 44108 KB Output is correct
6 Correct 24 ms 44048 KB Output is correct
7 Correct 24 ms 44180 KB Output is correct
8 Correct 28 ms 44116 KB Output is correct
9 Correct 27 ms 44152 KB Output is correct
10 Correct 27 ms 44108 KB Output is correct
11 Incorrect 29 ms 44132 KB Output isn't correct
12 Halted 0 ms 0 KB -