oj.uz

답안 #787420

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
787420 2023-07-19T07:22:53 Z 반딧불(#10031) 함박 스테이크 (JOI20_hamburg) C++17
2 / 100
 271 ms 34928 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

void input();
bool check1();
bool check2();
bool check3();
bool check4();
void output();

int main(){
    input();
    if(!check1()) if(!check2()) if(!check3()) check4();
    output();
}

int n, k;
vector<int> xCoord(1), yCoord(1);
int L[200002], R[200002], D[200002], U[200002], X, Y;
vector<pair<int, int> > ans;

void input(){
    scanf("%d %d", &n, &k);
    for(int i=1; i<=n; i++){
        scanf("%d %d %d %d", &L[i], &D[i], &R[i], &U[i]);
        xCoord.push_back(L[i]); xCoord.push_back(R[i]);
        yCoord.push_back(D[i]); yCoord.push_back(U[i]);
    }
    sort(xCoord.begin(), xCoord.end()); xCoord.erase(unique(xCoord.begin(), xCoord.end()), xCoord.end());
    sort(yCoord.begin(), yCoord.end()); yCoord.erase(unique(yCoord.begin(), yCoord.end()), yCoord.end());
    for(int i=1; i<=n; i++){
        L[i] = lower_bound(xCoord.begin(), xCoord.end(), L[i]) - xCoord.begin();
        R[i] = lower_bound(xCoord.begin(), xCoord.end(), R[i]) - xCoord.begin();
        D[i] = lower_bound(yCoord.begin(), yCoord.end(), D[i]) - yCoord.begin();
        U[i] = lower_bound(yCoord.begin(), yCoord.end(), U[i]) - yCoord.begin();
    }
    X = (int)xCoord.size()-1, Y = (int)yCoord.size()-1;
}

bool check1(){
    int maxX = 0, maxY = 0;
    for(int i=1; i<=n; i++) maxX = max(maxX, L[i]), maxY = max(maxY, D[i]);
    for(int i=1; i<=n; i++){
        if(maxX > R[i] || maxY > U[i]) return false;
    }
    ans.push_back(make_pair(maxX, maxY));
    return true;
}

struct namespace2{
    struct segTree{
        int n;
        ll a[400002], b[400002];

        void init(int _n){
            n = _n;
            for(int i=1; i<=n; i++) a[i] = b[i] = 0;
        }

        void addin(int x, ll va, ll vb){
            while(x<=n){
                a[x]+=va, b[x]+=vb;
                x+=x&-x;
            }
        }

        void add(int l, int r, ll v){
            addin(l, v, -v*(l-1));
            addin(r+1, 0, v*(r-l+1));
        }

        ll sum(int x){
            ll va = 0, vb = 0;
            while(x){
                va+=a[x], vb+=b[x];
                x-=x&-x;
            }
            return va*x+vb;
        }

        ll sum(int l, int r){
            return sum(r) - sum(l-1);
        }
    } treeA, treeB;

    struct Range{
        int L, R, D, U;
        Range(){
            L = D = 0;
            R = U = 1e9;
        }
        Range(int L, int R, int D, int U): L(L), R(R), D(D), U(U){}
        Range operator+(const Range &r)const{
            return Range(max(L,r.L), min(R,r.R), max(D,r.D), min(U,r.U));
        }
        bool valid(){
            return L<=R && D<=U;
        }
    } arr[200002];

    Range xLeft[400002], xRight[400002];
    Range yLeft[400002], yRight[400002];

    struct dat{
        int where, type, val;
        int l, r;
        dat(){}
        dat(int where, int type, int val, int l, int r): where(where), type(type), val(val), l(l), r(r){}
        bool operator<(const dat &nxt)const{
            if(val != nxt.val) return val<nxt.val;
            return type<nxt.type;
        }
    };

    vector<dat> vec;

    bool check2(){
        for(int i=1; i<=n; i++) arr[i] = Range(L[i], R[i], D[i], U[i]);
        for(int i=1; i<=n; i++){
            xRight[L[i]-1] = xRight[L[i]-1] + arr[i];
            xLeft[R[i]+1] = xLeft[R[i]+1] + arr[i];
            yRight[D[i]-1] = yRight[D[i]-1] + arr[i];
            yLeft[U[i]+1] = yRight[U[i]+1] + arr[i];
        }
        xLeft[0] = xRight[X+1] = yLeft[0] = yRight[Y+1] = Range(1, X, 1, Y);
        for(int i=1; i<=X+1; i++) xLeft[i] = xLeft[i] + xLeft[i-1];
        for(int i=1; i<=Y+1; i++) yLeft[i] = yLeft[i] + yLeft[i-1];
        for(int i=X; i>=0; i--) xRight[i] = xRight[i] + xRight[i+1];
        for(int i=Y; i>=0; i--) yRight[i] = yRight[i] + yRight[i+1];

        for(int i=1; i<=X; i++){
            Range tmp = xLeft[i-1] + xRight[i+1];
            if(tmp.valid()) vec.push_back(dat(0, 0, tmp.U, tmp.L, tmp.R)), vec.push_back(dat(0, 1, tmp.D, tmp.L, tmp.R));
        }
        for(int i=1; i<=Y; i++){
            Range tmp = yLeft[i-1] + yRight[i+1];
            if(tmp.valid()) vec.push_back(dat(1, 0, tmp.U, tmp.L, tmp.R)), vec.push_back(dat(1, 1, tmp.D, tmp.L, tmp.R));
        }
        sort(vec.begin(), vec.end());

        int X1 = -1, Y1 = -1;

        treeA.init(X), treeB.init(X);
        for(dat p: vec){
            if(p.type == 0){
                if(p.where == 0) treeA.add(p.l, p.r, 1);
                else             treeB.add(p.l, p.r, 1);
            }
            else{
                if(p.where == 0){
                    if(treeB.sum(p.l, p.r)){
                        Y1 = p.val;
                        for(int i=p.l; i<=p.r; i++) if(treeB.sum(i, i)) {X1 = i; break; }
                        assert(X1 != -1);
                        break;
                    }
                    treeA.add(p.l, p.r, -1);
                }
                else{
                    if(treeA.sum(p.l, p.r)){
                        Y1 = p.val;
                        for(int i=p.l; i<=p.r; i++) if(treeA.sum(i, i)) {X1 = i; break; }
                        assert(X1 != -1);
                        break;
                    }
                    treeB.add(p.l, p.r, -1);
                }
            }
        }
        if(Y1 == -1) return false;

        ans.push_back(make_pair(X1, Y1));
        Range p = xLeft[X1-1] + xRight[X1+1];
        Range q = yLeft[Y1-1] + yRight[Y1+1];
        p = p+q;
        ans.push_back(make_pair(p.L, p.D));
        return true;
    }
} p2;

bool check2(){
    return p2.check2();
}

bool check3(){
    return false;
}

bool check4(){
    return false;
}

void output(){
    if(ans.empty()) exit(1);
    while((int)ans.size() < k) ans.push_back(ans.back());
    for(auto p: ans) printf("%d %d\n", xCoord[p.first], yCoord[p.second]);
}

Compilation message

hamburg.cpp: In function 'void input()':
hamburg.cpp:26:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |     scanf("%d %d", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~
hamburg.cpp:28:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |         scanf("%d %d %d %d", &L[i], &D[i], &R[i], &U[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
1.0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 28500 KB Output is correct
2 Correct 17 ms 28500 KB Output is correct
3 Correct 17 ms 28504 KB Output is correct
4 Correct 15 ms 28500 KB Output is correct

Subtask #2
0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 14 ms 28628 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #3
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 17 ms 28628 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #4
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 13 ms 28628 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #5
1.0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 28500 KB Output is correct
2 Correct 17 ms 28500 KB Output is correct
3 Correct 17 ms 28504 KB Output is correct
4 Correct 15 ms 28500 KB Output is correct
5 Correct 258 ms 34920 KB Output is correct
6 Correct 271 ms 34928 KB Output is correct
7 Correct 263 ms 34868 KB Output is correct
8 Correct 261 ms 34904 KB Output is correct

Subtask #6
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 14 ms 28628 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #7
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 17 ms 28628 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #8
0 / 79.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 13 ms 28628 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -