제출 #1355945

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1355945		cnam9	Mixture (BOI20_mixture)	C++20	큐에 대기중	0 ms	0 KiB

Mixture

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#define inline inline __attribute__((always_inline))

using namespace std;

template <class Value, size_t MAX_SIZE>
class BufferedDeque {
    Value buf[MAX_SIZE];
    Value *begin = buf;
    Value *end = buf;

public:

    inline size_t size() const { return end - begin; }
    inline bool empty() const { return end == begin; }
    inline void clear() { begin = end = buf; }

    inline void push_back(const Value &value) { *end++ = value; }
    inline void pop_front() { begin++; }
    inline void pop_back() { end--; }

    inline Value &front() { return *begin; }
    inline Value &back() { return end[-1]; }

    inline const Value &front() const { return *begin; }
    inline const Value &back() const { return end[-1]; }
};

struct Frac {
    long long a, b;

    inline void operator-=(const Frac &other) {
        a = a * other.b - b * other.a;
    }

    friend ostream &operator<<(ostream &dest, const Frac &frac) {
        return dest << frac.a << '/' << frac.b;
    }

    inline Frac operator-() const {
        return {-a, b};
    }
};

struct Point {
    Frac x, y;

    inline Point operator-() const {
        return {-x, -y};
    }
};

inline bool cw(const Point &p, const Point &q) {
    return (__int128) p.x.a * q.y.a < (__int128) p.y.a * q.x.a;
}

inline bool ccw(const Point &p, const Point &q) {
    return (__int128) p.x.a * q.y.a > (__int128) p.y.a * q.x.a;
}

struct Compare {
    inline bool operator()(const Point &p, const Point &q) const {
        bool phalf = p.y.a ? p.y.a > 0 : p.x.a > 0;
        bool qhalf = q.y.a ? q.y.a > 0 : q.x.a > 0;

        return phalf != qhalf ? phalf > qhalf : ccw(p, q);
    }
};


constexpr int N = 1e5 + 5;

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    // freopen("input.txt", "r", stdin);

    int x, y, z;
    cin >> x >> y >> z;

    Point P{Frac{x, x + y + z}, Frac{y, x + y + z}};

    int q;
    cin >> q;

    int can1 = 0;
    long long can2 = 0;
    bool can3 = false;

    map<Point, int, Compare> cnt;

    auto prev = [&cnt](map<Point, int, Compare>::iterator it) {
        return it == cnt.begin() ? --cnt.end() : --it;
    };
    auto next = [&cnt](map<Point, int, Compare>::iterator it) {
        return ++it == cnt.end() ? cnt.begin() : it;
    };

    vector<Point> points;
    points.reserve(q);

    while (q--) {
        char type;
        cin >> type;

        if (type == 'A') {
            int x, y, z;
            cin >> x >> y >> z;

            Point p{Frac{x, x + y + z}, Frac{y, x + y + z}};
            p.x -= P.x;
            p.y -= P.y;
            points.push_back(p);
            
            if (p.x.a == 0 && p.y.a == 0) {
                can1++;
                goto reply;
            }

            auto [it, inserted] = cnt.try_emplace(p, 0);
            it->second++;
            if (inserted && cnt.size() > 1) {
                auto low = prev(it);
                auto high = next(it);

                if (cw(low->first, high->first) && !cw(low->first, p) && !cw(p, high->first)) {
                    can3 = true;
                }
            }

            it = cnt.find(-p);
            if (it != cnt.end()) can2 += it->second;
        } else {
            int i;
            cin >> i;

            const Point &p = points[i - 1];
            
            if (p.x.a == 0 && p.y.a == 0) {
                can1--;
                goto reply;
            }

            auto it = cnt.find(p);
            if (--(it->second) == 0) {
                auto high = cnt.erase(it);

                if (cnt.size() > 1) {
                    auto low = prev(high);

                    if (cw(low->first, high->first) && !cw(low->first, p) && !cw(p, high->first)) {
                        can3 = false;
                    }
                }
            }

            it = cnt.find(-p);
            if (it != cnt.end()) can2 -= it->second;
        }

    reply:
        cout << (can1 ? "1\n" : can2 ? "2\n" : can3 ? "3\n" : "0\n");
    }

    return 0;
}