oj.uz

답안 #667856

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
667856 2022-12-02T07:20:53 Z BlackJack Krave (COI14_krave) C++14
100 / 100
 806 ms 84208 KB 
#include<bits/stdc++.h>
using namespace std;

void DBG() { cerr << "]\n"; }
template<class H, class... T> void DBG(H h, T... t) {
    cerr << h; if(sizeof...(t)) cerr << ", ";
    DBG(t...);
}
#ifdef LOCAL
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
#define dbg(...) 0
#endif // LOCAL

#define FOR(i,a,b) for(int i = (a) ; i<(b) ; i++)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for(int i = (b)-1 ; i>=(a) ; i--)
#define R0F(i,a) ROF(i,0,a)
#define each(e,a) for(auto &e : (a))
#define sz(v) (int)(v).size()
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pb push_back
#define tcT template<class T
#define nl "\n"
#define fi first
#define se second

using ll = long long;
using vi = vector<int>;
using pi = pair<int,int>;
using str = string;
using db = long double;
tcT> using V = vector<T>;
tcT> using pqg = priority_queue<T,vector<T>,greater<T>>;

void setIO(string NAME = "") {
    cin.tie(0)->sync_with_stdio(0);
    if(sz(NAME)) {
        freopen((NAME + ".inp").c_str(),"r",stdin);
        freopen((NAME + ".out").c_str(),"w",stdout);
    }
}

tcT> bool ckmin(T&a, const T&b) {
    return b < a ? a=b,1 : 0; }
tcT> bool ckmax(T&a, const T&b) {
    return b > a ? a=b,1 : 0; }

const int MOD = 1e9 + 7;
const ll INF = 1e18;

const int MX = 1e5+5;

struct SegTree {
    set<int> seg[MX*4 + 7];
    int N;
    void init(int _SZ) {
        N = _SZ;
    }
    void addPoint(int l, int r, int pos, int ind, int L, int R) {
        if(l > R || r < L) return;
        if(l <= L && R <= r) {
            seg[ind].insert(pos);
            return;
        }
        int mid = (L + R) >> 1;
        addPoint(l, r, pos, ind<<1, L, mid);
        addPoint(l, r, pos, ind<<1|1, mid+1, R);
    }
    void addPoint(int l, int r, int pos) {
        addPoint(l, r, pos, 1, 0, N);
    }

    int query(int pos, int val, int ind, int L, int R) {
        if(R < pos || pos < L) return -1;
        auto it = seg[ind].upper_bound(val);
        int res = -1;
        if(it != seg[ind].begin()) {
            it--;
            res = *it;
        }

        if(L == R) return res;
        int mid = (L + R) >> 1;

        if(pos <= mid) ckmax(res, query(pos, val, ind<<1, L, mid));
        else ckmax(res, query(pos, val, ind<<1|1, mid+1, R));
        return res;
    }

    int query(int pos, int val) {
        return query(pos, val, 1, 0, N);
    }
};

struct Rect {
    int xl, yl, xr, yr;
    ll getArea() { return 1LL*(xr - xl)*(yr - yl); }
    Rect(int _xl = 0, int _yl = 0, int _xr = 0, int _yr = 0) {
        xl = _xl;
        yl = _yl;
        xr = _xr;
        yr = _yr;
    }
    bool operator<(const Rect&rhs) const {
        if(xl != rhs.xl) return xl < rhs.xl;
        return yl < rhs.yl;
    }
};

int A, B;

int N;

SegTree stX, stY;

set<Rect> s;

void solve() {
    cin >> A >> B;
    stY.init(A);
    stX.init(B);
    stY.addPoint(0, A, 0);
    stX.addPoint(0, B, 0);
    s.insert(Rect(0, 0, A, B));
    cin >> N;
    while(N-- > 0) {
        int x, y, dir;
        cin >> x >> y >> dir;
        int rect_y = stY.query(x, y), rect_x = stX.query(y, x);


        assert(rect_y >= 0 && rect_x >= 0);

        auto it = s.lower_bound(Rect(rect_x, rect_y, -1, -1));

        int xl = it->xl, yl = it->yl, xr = it->xr, yr = it->yr;

        s.erase(it);

        Rect newA, newB;

        if(dir == 1) {
            newA = Rect(xl, yl, xr, y);
            newB = Rect(xl, y, xr, yr);
            stY.addPoint(xl, xr, y);
        }
        else {
            newA = Rect(xl, yl, x, yr);
            newB = Rect(x, yl, xr, yr);
            stX.addPoint(yl, yr, x);
        }

        cout << min(newA.getArea(), newB.getArea()) << " " << max(newA.getArea(), newB.getArea()) << nl;

        s.insert(newA);
        s.insert(newB);
    }
}

int main() {
    setIO();

    int t=1;
    //cin>>t;
    while(t-->0) {
        solve();
    }

    return 0;
}

Compilation message

krave.cpp: In function 'void setIO(std::string)':
krave.cpp:40:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |         freopen((NAME + ".inp").c_str(),"r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
krave.cpp:41:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |         freopen((NAME + ".out").c_str(),"w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 37972 KB Output is correct
2 Correct 21 ms 37884 KB Output is correct

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 38340 KB Output is correct
2 Correct 24 ms 38732 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 135 ms 45844 KB Output is correct
2 Correct 123 ms 47580 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 137 ms 45824 KB Output is correct
2 Correct 136 ms 48960 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 125 ms 45872 KB Output is correct
2 Correct 151 ms 50508 KB Output is correct

Subtask #6
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 301 ms 54532 KB Output is correct
2 Correct 354 ms 71116 KB Output is correct

Subtask #7
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 795 ms 72080 KB Output is correct
2 Correct 417 ms 76492 KB Output is correct

Subtask #8
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 774 ms 71276 KB Output is correct
2 Correct 315 ms 79272 KB Output is correct
3 Correct 164 ms 51656 KB Output is correct
4 Correct 366 ms 79056 KB Output is correct

Subtask #9
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 806 ms 72304 KB Output is correct
2 Correct 361 ms 83272 KB Output is correct
3 Correct 169 ms 51880 KB Output is correct
4 Correct 375 ms 81796 KB Output is correct

Subtask #10
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 695 ms 72700 KB Output is correct
2 Correct 256 ms 72992 KB Output is correct
3 Correct 157 ms 51968 KB Output is correct
4 Correct 392 ms 84208 KB Output is correct