Submission #961772

#	Time	Username	Problem	Language	Result	Execution time	Memory
961772		Vladth11	Hamburg Steak (JOI20_hamburg)	C++14	15 / 100	139 ms	36116 KiB

hamburg

#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")

#define int ll

using namespace std;
typedef long long ll;
typedef pair <ll, ll> pii;

const ll NMAX = 200005;
const ll INF = 1e9;
const ll nrbits = 20;
const ll MOD = 998244353;

struct rect {
    int x1, y1, x2, y2;
} v[NMAX];

int n, k;
vector <pii> sol;
int taken[NMAX];

rect intersect(rect a, rect b) {
    rect sol = {max(a.x1, b.x1), max(a.y1, b.y1), min(a.x2, b.x2), min(a.y2, b.y2)};
    return sol;
}

bool isIn(pii a, rect r) {
    return (r.x1 <= a.first && a.first <= r.x2 && r.y1 <= a.second && a.second <= r.y2);
}

rect solve1() {
    int i;
    rect sol = {0, 0, INF, INF};
    for(i = 1; i <= n; i++) {
        sol = intersect(sol, v[i]);
    }
    return sol;
}

void afiseaza() {
    for(auto x : sol) {
        cout << x.first << " " << x.second << "\n";
    }
    k -= sol.size();
    while(k--) {
        cout << "0 0\n";
    }
    exit(0);
}

void tryy(int lvl) {
    int i;
    if(lvl == 0) {
        int ok = 1;
        for(i = 1; i <= n; i++) {
            ok &= (taken[i] > 0);
        }
        if(ok) {
            afiseaza();
        }
        return;
    }
    int xmin = INF, xmax = 0, ymin = INF, ymax = 0;
    for(i = 1; i <= n; i++) {
        if(taken[i]) continue;
        xmin = min(xmin, v[i].x2);
        xmax = max(xmax, v[i].x1);
        ymin = min(ymin, v[i].y2);
        ymax = max(ymax, v[i].y1);
    }
    vector <pii> per;
    per.push_back({xmin, ymin});
    per.push_back({xmin, ymax});
    per.push_back({xmax, ymin});
    per.push_back({xmax, ymax});
    for(int d = 0; d < 4; d++) {
        pii acum = per[d];
        for(i = 1; i <= n; i++) {
            if(isIn(acum, v[i])) {
                taken[i]++;
            }
        }
        sol.push_back(acum);
        tryy(lvl - 1);
        for(i = 1; i <= n; i++) {
            if(isIn(acum, v[i])) taken[i]--;
        }
        sol.pop_back();
    }
}

vector <int> nrmX;
vector <int> nrmY;
int codedX[NMAX];
int codedY[NMAX];
unordered_map <int, int> mpX;
unordered_map <int, int> mpY;

vector <int> ev1[NMAX];
vector <int> ev2[NMAX];
vector <int> ev3[NMAX];
vector <int> ev4[NMAX];

int sum1[NMAX];
int sum2[NMAX];
int sum3[NMAX];
int sum4[NMAX];

int f[NMAX];

struct ura {
    int unu, doi, trei, patru;
} plec[NMAX];

void add(int x, int val) {
    if(plec[x].unu != -1) {
        sum1[plec[x].unu] += val;
    }
    if(plec[x].doi != -1) {
        sum2[plec[x].doi] += val;
    }
    if(plec[x].trei != -1) {
        sum3[plec[x].trei] += val;
    }
    if(plec[x].patru != -1) {
        sum4[plec[x].patru] += val;
    }
}

signed main() {
#ifdef HOME
    ifstream cin(".in");
    ofstream cout(".out");
#endif // HOME
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int i;
    cin >> n >> k;
    for(i = 1; i <= n; i++) {
        cin >> v[i].x1 >> v[i].y1 >> v[i].x2 >> v[i].y2; /// it doesn't matter
    }
    /// K = 1?
    tryy(1);
    /// K = 2?
    tryy(2);
    /// K = 3?
    tryy(3);
    /// K = 4 and pair found
    tryy(4);
    for(i = 1; i <= n; i++) {
        nrmX.push_back(v[i].x1);
        nrmX.push_back(v[i].x2);
        nrmY.push_back(v[i].y2);
        nrmY.push_back(v[i].y1);
    }
    sort(nrmX.begin(), nrmX.end());
    sort(nrmY.begin(), nrmY.end());
    int cnt = 0;
    int lst = -1;
    for(auto x : nrmX) {
        if(x != lst) {
            cnt++;
        }
        mpX[x] = cnt;
        codedX[cnt] = x;
        lst = x;
    }
    cnt = 0;
    lst = -1;
    for(auto x : nrmY) {
        if(x != lst) {
            cnt++;
        }
        mpY[x] = cnt;
        codedY[cnt] = x;
        lst = x;
    }
    for(i = 1; i <= n; i++) {
        v[i].x1 = mpX[v[i].x1];
        v[i].x2 = mpX[v[i].x2];
        v[i].y1 = mpY[v[i].y1];
        v[i].y2 = mpY[v[i].y2];
    }
    int x1 = INF, x2 = 0, y1 = INF, y2 = 0;
    for(i = 1; i <= n; i++) {
        x1 = min(x1, v[i].x2);
        x2 = max(x2, v[i].x1);
        y1 = min(y1, v[i].y2);
        y2 = max(y2, v[i].y1);
    }
    pii unu = {x1, y1};
    pii doi = {x2, y1};
    pii trei = {x2, y2};
    pii patru = {x1, y2};
    int total = 0;
    for(i = 1; i <= n; i++) {
        plec[i] = {-1, -1, -1, -1};
        if(v[i].y1 <= y1 && v[i].y2 >= y1) {
            int st = max(unu.first, v[i].x1);
            int dr = v[i].x2 + 1;
            assert(st <= dr);
            if(st <= x2) {
                ev1[st].push_back(i);
            }
            if(dr <= x2) {
                ev1[dr].push_back(-i);
                plec[i].unu = v[i].x2;
                sum1[v[i].x2]++;
            }
        }
        if(v[i].x1 <= doi.first && v[i].x2 >= doi.first) {
            int st = max(doi.second, v[i].y1);
            int dr = v[i].y2 + 1;
            assert(st <= dr);
            if(st <= y2) {
                ev2[st].push_back(i);
            }
            if(dr <= y2) {
                ev2[dr].push_back(-i);
                plec[i].doi = v[i].y2;
                sum2[v[i].y2]++;
            }
        }
        if(v[i].y1 <= trei.second && v[i].y2 >= trei.second) {
            int st = min(trei.first, v[i].x2);
            int dr = v[i].x1 - 1;
            assert(st >= dr);
            if(st >= x1) {
                ev3[st].push_back(i);
            }
            if(dr >= x1) {
                ev3[dr].push_back(-i);
                plec[i].trei = v[i].x1;
                sum3[v[i].x1]++;
            }
        }
        if(v[i].x1 <= patru.first && v[i].x2 >= patru.first) {
            int st = min(patru.second, v[i].y2);
            int dr = v[i].y1 - 1;
            assert(st >= dr);
            if(st >= y1) {
                ev4[st].push_back(i);
            }
            if(dr >= y1) {
                ev4[dr].push_back(-i);
                plec[i].patru = v[i].y1;
                sum4[v[i].y1]++;
            }
        }
    }
    for(i = 1; i <= n; i++) {
        int x = i;
        if(isIn(unu, v[i])) {
            f[x]++;
            if(f[x] == 1) total++;
            if(f[x] == 2) {
                add(x, -1);
            }
        }
        if(isIn(doi, v[i])) {
            f[x]++;
            if(f[x] == 1) total++;
            if(f[x] == 2) {
                add(x, -1);
            }
        }
        if(isIn(trei, v[i])) {
            f[x]++;
            if(f[x] == 1) total++;
            if(f[x] == 2) {
                add(x, -1);
            }
        }
        if(isIn(patru, v[i])) {
            f[x]++;
            if(f[x] == 1) total++;
            if(f[x] == 2) {
                add(x, -1);
            }
        }
    }
    while(unu.first <= x2) {
        if(unu.first != x1) {
            for(auto x : ev1[unu.first]) {
                if(x > 0) {
                    f[x]++;
                    if(f[x] == 1) total++;
                    if(f[x] == 2) {
                        add(x, -1);
                    }
                } else {
                    f[-x]--;
                    if(f[-x] == 0) total--;
                    if(f[-x] == 1) {
                        add(-x, 1);
                    }
                }
            }
        }
        while(doi.second < y2 && sum2[doi.second] == 0) {
            doi.second++;
            for(auto x : ev2[doi.second]) {
                if(x > 0) {
                    f[x]++;
                    if(f[x] == 1) total++;
                    if(f[x] == 2) {
                        add(x, -1);
                    }
                } else {
                    f[-x]--;
                    if(f[-x] == 0) total--;
                    if(f[-x] == 1) {
                        add(-x, 1);
                    }
                }
            }
        }
        while(trei.first > x1 && sum3[trei.first] == 0) {
            trei.first--;
            for(auto x : ev3[trei.first]) {
                if(x > 0) {
                    f[x]++;
                    if(f[x] == 1) total++;
                    if(f[x] == 2) {
                        add(x, -1);
                    }
                } else {
                    f[-x]--;
                    if(f[-x] == 0) total--;
                    if(f[-x] == 1) {
                        add(-x, 1);
                    }
                }
            }
        }

        while(patru.second > y1 && sum4[patru.second] == 0) {
            patru.second--;
            for(auto x : ev4[patru.second]) {
                if(x > 0) {
                    f[x]++;
                    if(f[x] == 1) total++;
                    if(f[x] == 2) {
                        add(x, -1);
                    }
                } else {
                    f[-x]--;
                    if(f[-x] == 0) total--;
                    if(f[-x] == 1) {
                        add(-x, 1);
                    }
                }
            }
        }
        if(total == n) {
            cout << codedX[unu.first] << " " << codedY[unu.second] << "\n";
            cout << codedX[doi.first] << " " << codedY[doi.second] << "\n";
            cout << codedX[trei.first] << " " << codedY[trei.second] << "\n";
            cout << codedX[patru.first] << " " << codedY[patru.second] << "\n";
            return 0;
        }
        unu.first++;
    }
    return 0;
}

• Subtask 1: 1 / 1
• Subtask 2: 1 / 1
• Subtask 3: 3 / 3
• Subtask 4: 0 / 6
• Subtask 5: 1 / 1
• Subtask 6: 3 / 3
• Subtask 7: 6 / 6
• Subtask 8: 0 / 79