Submission #1265188

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265188		cpismylifeOwO	Mixture (BOI20_mixture)	C++20	13 / 100	1 ms	328 KiB

Mixture

#include <bits/stdc++.h>

using namespace std;

const long long mod = 1e9 + 7;
const int MaxN = 1e6 + 5;

long long GCD(long long a, long long b)
{
    long long t;
    while (b > 0)
    {
        t = b;
        b = a % b;
        a = t;
    }
    return a;
}

struct Bottle
{
    long long a, b, c;

    Bottle() = default;

    Bottle(long long _a, long long _b, long long _c)
    {
        long long d = GCD(GCD(_a, _b), _c);
        a = _a / d;
        b = _b / d;
        c = _c / d;
    }

    bool operator == (const Bottle& other) const
    {
        return (this->a == other.a) && (this->b == other.b) && (this->c == other.c);
    }
};

long long s, g, p, q;
int n;
Bottle arr[MaxN];

void Inp()
{
    cin >> s >> g >> p >> q;
}

struct Fraction
{
    long long a, b;

    Fraction(long long _a, long long _b)
    {
        a = _a;
        b = _b;
    }

    Fraction& operator = (const Fraction& other)
    {
        this->a = other.a;
        this->b = other.b;
        return *this;
    }

    bool operator == (const Fraction& other) const
    {
        return this->a * other.b == this->b * other.a;
    }

    bool operator < (const Fraction& other) const
    {
        return (long double)((long double)this->a / this->b) < (long double)((long double)other.a / other.b);
    }

    bool operator > (const Fraction& other) const
    {
        return (long double)((long double)this->a / this->b) > (long double)((long double)other.a / other.b);
    }
};

int cnts, cntt;
int cnt[2][2];
Bottle sam;
map<Fraction, int> frac[2];
multiset<Fraction> fr[2];
multiset<Fraction> revfr[2];
int mark[2][2];
long long cnts2;

void Add(bool rev, int p)
{
    if (arr[p].a == 0 && arr[p].b == 0 && arr[p].c == 0)
    {
        return;
    }
    cntt += rev * (-1) + (!rev);
    long long a = (arr[p].a * sam.b - arr[p].b * sam.a), b = (arr[p].b * sam.c - arr[p].c * sam.b);
    //cout << a << " " << b << endl;
    if (a == 0 && b == 0)
    {
        cnts += rev * (-1) + (!rev);
        return;
    }
    Fraction f = Fraction(b, a);
    if (a == 0)
    {
        cnt[0][b < 0] += rev * (-1) + (!rev);
        if (rev)
        {
            revfr[b < 0].erase(revfr[b < 0].lower_bound(Fraction(a, b)));
        }
        else
        {
            revfr[b < 0].insert(Fraction(a, b));
        }
        return;
    }
    if (b == 0)
    {
        cnt[1][a < 0] += rev * (-1) + (!rev);
        if (rev)
        {
            fr[a < 0].erase(fr[a < 0].lower_bound(f));
        }
        else
        {
            fr[a < 0].insert(f);
        }
        return;
    }
    mark[a < 0][b < 0] += rev * (-1) + (!rev);
    if (!rev)
    {
        frac[a < 0][f]++;
        cnts2 += frac[a > 0][f];
        fr[a < 0].insert(f);
        revfr[b < 0].insert(Fraction(a, b));
    }
    else
    {
        frac[a < 0][f]--;
        cnts2 -= frac[a > 0][f];
        fr[a < 0].erase(fr[a < 0].lower_bound(f));
        revfr[b < 0].erase(revfr[b < 0].lower_bound(Fraction(a, b)));
    }
}

bool Check2()
{
    if (cntt < 2)
    {
        return false;
    }
    if (cnt[0][0] > 0 && cnt[0][1] > 0)
    {
        return true;
    }
    if (cnt[1][0] > 0 && cnt[1][1] > 0)
    {
        return true;
    }
    return cnts2 > 0;
}

bool Check3()
{
    if (cntt < 3)
    {
        return false;
    }
    for (int x = 0; x < 2; x++)
    {
        for (int y = 0; y < 2; y++)
        {
            if (cnt[0][x] > 0 && cnt[1][y] > 0 && mark[y ^ 1][x ^ 1] > 0)
            {
                return true;
            }
        }
    }
    if (!fr[0].empty() && !fr[1].empty())
    {
        auto p = fr[1].lower_bound(*fr[0].begin()), q = fr[1].lower_bound(*(--fr[0].end()));
        if (p != q)
        {
            return true;
        }
        p = fr[0].lower_bound(*fr[1].begin());
        q = fr[0].lower_bound(*(--fr[1].end()));
        if (p != q)
        {
            return true;
        }
    }
    if (revfr[0].empty() || revfr[1].empty())
    {
        return false;
    }
    auto p = revfr[1].lower_bound(*revfr[0].begin()), q = revfr[1].lower_bound(*(--revfr[0].end()));
    if (p != q)
    {
        return true;
    }
    p = revfr[0].lower_bound(*revfr[1].begin());
    q = revfr[0].lower_bound(*(--revfr[1].end()));
    return p != q;
}

void Edge1()
{
    int cnt = 0;
    for (int x = 1; x <= q; x++)
    {
        //cout << x << endl;
        char t;
        cin >> t;
        if (t == 'A')
        {
            n++;
            long long a, b, c;
            cin >> a >> b >> c;
            arr[n] = Bottle(a, b, c);
            cnt += (arr[n].a == 0 && arr[n].b == 0 && arr[n].c == 0);
        }
        else
        {
            int p;
            cin >> p;
            cnt -= (arr[p].a == 0 && arr[p].b == 0 && arr[p].c == 0);
        }
        cout << (cnt > 0) << "\n";
    }
}

bool Check(long long a, long long b)
{
    if (b == 0)
    {
        return a == 0;
    }
    return a > 0 && a % b == 0;
}

void Edge2()
{
    int cnt = 0, cnt2 = 0;
    for (int x = 1; x <= q; x++)
    {
        //cout << x << endl;
        char t;
        cin >> t;
        if (t == 'A')
        {
            n++;
            long long a, b, c;
            cin >> a >> b >> c;
            arr[n] = Bottle(a, b, c);
            if (arr[n].a != 0 || arr[n].b != 0 || arr[n].c != 0)
            {
                cnt += ((sam.a != 0 || arr[n].a == 0) && (sam.b != 0 || arr[n].b == 0) && (sam.c != 0 || arr[n].c == 0));
                cnt2 += (Check(arr[n].a, sam.a) && Check(arr[n].b, sam.b) && Check(arr[n].c, sam.c));
            }
        }
        else
        {
            int p;
            cin >> p;
            if (arr[p].a != 0 || arr[p].b != 0 || arr[p].c != 0)
            {
                cnt -= ((sam.a != 0 || arr[p].a == 0) && (sam.b != 0 || arr[p].b == 0) && (sam.c != 0 || arr[p].c == 0));
                cnt2 -= (Check(arr[p].a, sam.a) && Check(arr[p].b, sam.b) && Check(arr[p].c, sam.c));
            }
        }
        //cout << cnt << " " << cnt2 << "\n";
        if (cnt2 > 0)
        {
            cout << 1 << "\n";
        }
        else
        {
            cout << 2 * (cnt > 0) << "\n";
        }
    }
}

bool Checkk(long long a, long long b)
{
    return (b != 0) || (a == 0);
}

void Edge3()
{
    int cnta[2] = {0, 0};
    int pp = 0;
    for (int x = 1; x <= q; x++)
    {
        //cout << x << endl;
        char t;
        cin >> t;
        if (t == 'A')
        {
            n++;
            long long a, b, c;
            cin >> a >> b >> c;
            arr[n] = Bottle(a, b, c);
            if (Checkk(arr[n].a, sam.a) && Checkk(arr[n].b, sam.b) && Checkk(arr[n].c, sam.c))
            {
                if (sam.a == 0)
                {
                    long long a = arr[n].b * sam.c - arr[n].c * sam.b;
                    //cout << a << " ";
                    if (a != 0)
                    {
                        cnta[a < 0]++;
                    }
                    if (Check(arr[n].a, sam.a) && Check(arr[n].b, sam.b) && Check(arr[n].c, sam.c) && (sam.b / arr[n].b) == (sam.c / arr[n].c))
                    {
                        pp++;
                    }
                }
                if (sam.b == 0)
                {
                    long long a = arr[n].a * sam.c - arr[n].c * sam.a;
                    //cout << a << " ";
                    if (a != 0)
                    {
                        cnta[a < 0]++;
                    }
                    if (Check(arr[n].a, sam.a) && Check(arr[n].b, sam.b) && Check(arr[n].c, sam.c) && (sam.a / arr[n].a) == (sam.c / arr[n].c))
                    {
                        pp++;
                    }
                }
                if (sam.c == 0)
                {
                    long long a = arr[n].a * sam.b - arr[n].b * sam.a;
                    //cout << a << " ";
                    if (a != 0)
                    {
                        cnta[a < 0]++;
                    }
                    if (Check(arr[n].a, sam.a) && Check(arr[n].b, sam.b) && Check(arr[n].c, sam.c) && (sam.a / arr[n].a) == (sam.b / arr[n].b))
                    {
                        pp++;
                    }
                }
            }
        }
        else
        {
            int p;
            cin >> p;
            if (Checkk(arr[p].a, sam.a) && Checkk(arr[p].b, sam.b) && Checkk(arr[p].c, sam.c))
            {
                if (sam.a == 0)
                {
                    long long a = arr[p].b * sam.c - arr[p].c * sam.b;
                    if (a != 0)
                    {
                        cnta[a < 0]--;
                    }
                    if (Check(arr[p].a, sam.a) && Check(arr[p].b, sam.b) && Check(arr[p].c, sam.c) && (sam.b / arr[p].b) == (sam.c / arr[p].c))
                    {
                        pp--;
                    }
                }
                if (sam.b == 0)
                {
                    long long a = arr[p].a * sam.c - arr[p].c * sam.a;
                    if (a != 0)
                    {
                        cnta[a < 0]--;
                    }
                    if (Check(arr[p].a, sam.a) && Check(arr[p].b, sam.b) && Check(arr[p].c, sam.c) && (sam.a / arr[p].a) == (sam.c / arr[p].c))
                    {
                        pp--;
                    }
                }
                if (sam.c == 0)
                {
                    long long a = arr[p].a * sam.b - arr[p].b * sam.a;
                    if (a != 0)
                    {
                        cnta[a < 0]--;
                    }
                    if (Check(arr[p].a, sam.a) && Check(arr[p].b, sam.b) && Check(arr[p].c, sam.c) && (sam.a / arr[p].a) == (sam.b / arr[p].b))
                    {
                        pp--;
                    }
                }
            }
        }
        //cout << Check(arr[n].c, sam.c) << " ";
        if (pp > 0)
        {
            cout << 1 << "\n";
        }
        else
        {
            cout << 2 * (cnta[0] > 0 && cnta[1] > 0) << "\n";
        }
    }
}

void Exc()
{
    int kk = (s == 0) + (g == 0) + (p == 0);
    sam = Bottle(s, g, p);
    if (kk == 3)
    {
        Edge1();
        return;
    }
    if (kk == 2)
    {
         Edge2();
         return;
    }
    if (kk == 1)
    {
        Edge3();
        return;
    }
    long long d = GCD(GCD(s, g), p);
    s /= d;
    g /= d;
    p /= d;
    sam = Bottle(s, g, p);
    cnts = n = 0;
    for (int x = 1; x <= q; x++)
    {
        //cout << x << endl;
        char t;
        cin >> t;
        if (t == 'A')
        {
            n++;
            long long a, b, c;
            cin >> a >> b >> c;
            arr[n] = Bottle(a, b, c);
            Add(false, n);
        }
        else
        {
            int p;
            cin >> p;
            Add(true, p);
        }
        if (cnts > 0)
        {
            cout << 1 << "\n";
            continue;
        }
        if (Check2())
        {
            cout << 2 << "\n";
            continue;
        }
        if (Check3())
        {
            cout << 3 << "\n";
            continue;
        }
        cout << 0 << "\n";
    }
}

int main()
{
    //freopen("MIXTURE.INP", "r", stdin);
    //freopen("MIXTURE.OUT", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int test = 1;
    //cin >> test;
    for (int x = 1; x <= test; x++)
    {
        Inp();
        Exc();
    }
    return 0;
}

• Subtask 1: 13 / 13
• Subtask 2: 0 / 17
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40