oj.uz

Submission #445036

# Submission time Handle Problem Language Result Execution time Memory
445036 2021-07-16T09:54:57 Z lohacho Matching (COCI20_matching) C++14
18 / 110
 31 ms 44988 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(x[val][0], x[val][1]), max(x[val][0], x[val][1]), 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(y[val][0], y[val][1]), max(y[val][0], y[val][1]), 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){
            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{
            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);
            }
        }
        ++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 25 ms 44108 KB Output is correct
2 Correct 25 ms 44144 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 44108 KB Output is correct
2 Correct 25 ms 44144 KB Output is correct
3 Correct 26 ms 44092 KB Output is correct
4 Correct 26 ms 44100 KB Output is correct
5 Correct 26 ms 44076 KB Output is correct
6 Correct 22 ms 44108 KB Output is correct
7 Correct 22 ms 44072 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 44108 KB Output is correct
2 Correct 25 ms 44144 KB Output is correct
3 Correct 26 ms 44092 KB Output is correct
4 Correct 26 ms 44100 KB Output is correct
5 Correct 26 ms 44076 KB Output is correct
6 Correct 22 ms 44108 KB Output is correct
7 Correct 22 ms 44072 KB Output is correct
8 Correct 28 ms 44108 KB Output is correct
9 Correct 31 ms 44080 KB Output is correct
10 Correct 27 ms 44200 KB Output is correct
11 Correct 23 ms 44108 KB Output is correct
12 Correct 29 ms 44136 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 44108 KB Output is correct
2 Correct 25 ms 44144 KB Output is correct
3 Correct 26 ms 44092 KB Output is correct
4 Correct 26 ms 44100 KB Output is correct
5 Correct 26 ms 44076 KB Output is correct
6 Correct 22 ms 44108 KB Output is correct
7 Correct 22 ms 44072 KB Output is correct
8 Correct 28 ms 44108 KB Output is correct
9 Correct 31 ms 44080 KB Output is correct
10 Correct 27 ms 44200 KB Output is correct
11 Correct 23 ms 44108 KB Output is correct
12 Correct 29 ms 44136 KB Output is correct
13 Incorrect 31 ms 44988 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 44108 KB Output is correct
2 Correct 25 ms 44144 KB Output is correct
3 Correct 26 ms 44092 KB Output is correct
4 Correct 26 ms 44100 KB Output is correct
5 Correct 26 ms 44076 KB Output is correct
6 Correct 22 ms 44108 KB Output is correct
7 Correct 22 ms 44072 KB Output is correct
8 Correct 28 ms 44108 KB Output is correct
9 Correct 31 ms 44080 KB Output is correct
10 Correct 27 ms 44200 KB Output is correct
11 Correct 23 ms 44108 KB Output is correct
12 Correct 29 ms 44136 KB Output is correct
13 Incorrect 31 ms 44988 KB Output isn't correct
14 Halted 0 ms 0 KB -