Submission #1263391

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263391		niepamietamhasla	Mixture (BOI20_mixture)	C++20	100 / 100	322 ms	47460 KiB

Mixture

#include <bits/stdc++.h>
using namespace std;

// Use __int128 for all heavy arithmetic
typedef __int128 i128;
typedef long long ll; // keep for reading q/counters from stdin

// array size
const int MAXN = 100000 + 5;

struct d {
    i128 a;
    i128 b;
    i128 S;
};

d pts[MAXN];
d cel;

//
// gcd for __int128
//
i128 gcd128(i128 a, i128 b) {
    if (a < 0) a = -a;
    if (b < 0) b = -b;
    while (b != 0) {
        i128 r = a % b;
        a = b;
        b = r;
    }
    return a >= 0 ? a : -a;
}

d przemien(i128 a, i128 b, i128 c) {
    i128 S = a + b + c;
    i128 G = gcd128(a, gcd128(b, S));
    if (G == 0) return {0,0,0};
    return {a / G, b / G, S / G};
}

void wypisztrojke(d u){
    // debug printing of __int128 (disabled by default)
    // auto print128 = [](i128 x){
    //     if(x==0){ cout<<"0"; return; }
    //     bool neg = x < 0;
    //     if(neg) x = -x;
    //     string s;
    //     while(x > 0){
    //         int digit = int(x % 10);
    //         s.push_back(char('0' + digit));
    //         x /= 10;
    //     }
    //     if(neg) cout << "-";
    //     reverse(s.begin(), s.end());
    //     cout << s;
    // };
    // cout << "("; print128(u.b); cout << ", "; print128(u.a); cout << ")   para\n";
}

struct comp {
    bool operator()(const d &d1, const d &d2) const {
        if (d1.a != d2.a) return d1.a < d2.a;
        if (d1.b != d2.b) return d1.b < d2.b;
        if (d1.S != d2.S) return d1.S < d2.S;
        return false;
    }
};

// maps and counters (use __int128 for numeric values)
map<d, i128, comp> ile;
map<d, i128, comp> M;
typedef pair<i128, i128> pii128;
map<pii128, i128> nad;
map<pii128, i128> pod;

i128 lewozero = 0;
i128 prawozero = 0;
i128 ilewiekszych = 0;
i128 ileprostych = 0;

//
// convexity / orientation using __int128
//
int wypuklosc(const d &d1, const d &d2, const d &d3) {
    // returns -1,0,1
    i128 v = d3.a * d1.b - d1.a * d3.b;
    if (v < 0) return -1;
    if (v > 0) return 1;
    return 0;
}

struct comp2 {
    bool operator()(const d &d1, const d &d2) const {
        bool up1 = (d1.a > 0) || (d1.a == 0 && d1.b > 0);
        bool up2 = (d2.a > 0) || (d2.a == 0 && d2.b > 0);
        if (up1 != up2) return up1;

        int o = wypuklosc(d1, {0,0,1}, d2);
        if (o != 0) return o > 0;

        if (d1.a != d2.a) return d1.a * d2.S < d2.a * d1.S;
        if (d1.b != d2.b) return d1.b * d2.S < d2.b * d1.S;
        return d1.S < d2.S;
    }
};

multiset<d, comp2> proste;

int wypuklosc2(const d &d1, const d &d2, const d &d3) {
    // similar logic as original, adapted to __int128
    i128 v = d3.a * d1.b - d1.a * d3.b;
    if (v < 0) return -1;
    if (v > 0) return 1;

    if (d1.a == 0 && d3.a == 0) return 1;
    if ((d1.a > 0 && d3.a < 0) || (d1.a < 0 && d3.a > 0)) return 1;

    auto it = proste.lower_bound(d1);
    ++it;
    if (it == proste.end()) {
        return -1;
    } else {
        return 1;
    }
}

bool c1 = false, c2 = false, c3 = false;

void dodajprosta(d punkt) {
    if (proste.size() < 2) {
        if (proste.size() == 0) ilewiekszych = 1;
        else {
            if (c2) ilewiekszych = 0;
            else ilewiekszych = 1;
        }
        proste.insert(punkt);
        return;
    }

    auto nxt = proste.lower_bound(punkt);
    if (nxt == proste.end()) nxt = proste.begin();

    auto prev = nxt;
    if (prev == proste.begin()) {
        prev = --(proste.end());
    } else {
        --prev;
    }

    if (wypuklosc2(*prev, {0,0,1}, *nxt) == -1) {
        ilewiekszych--;
    }

    proste.insert(punkt);

    if (wypuklosc2(*prev, {0,0,1}, punkt) == -1) ilewiekszych++;
    if (wypuklosc2(punkt, {0,0,1}, *nxt) == -1) ilewiekszych++;

    return;
}

void usunprosta(d punkt) {
    if (proste.size() <= 3) {
        if (proste.size() == 3) {
            if (c2) ilewiekszych = 0;
            else ilewiekszych = 1;
        } else if (proste.size() == 2) ilewiekszych = 1;
        else ilewiekszych = 0;
        auto it = proste.find(punkt);
        if (it != proste.end()) proste.erase(it);
        return;
    }

    auto x = proste.find(punkt);
    if (x == proste.end()) return; // nothing to erase

    auto prev = x;
    if (prev == proste.begin()) prev = --(proste.end());
    else --prev;

    auto nxt = x;
    ++nxt;
    if (nxt == proste.end()) nxt = proste.begin();

    if (wypuklosc2(*prev, {0,0,1}, punkt) == -1) ilewiekszych--;
    if (wypuklosc2(punkt, {0,0,1}, *nxt) == -1) ilewiekszych--;

    auto it = proste.find(punkt);
    if (it != proste.end()) proste.erase(it);

    if (wypuklosc2(*prev, {0,0,1}, *nxt) == -1) ilewiekszych++;

    return;
}

void dodaj(d punkt) {
    if (ile[punkt] > 0) {
        ile[punkt]++;
        return;
    }
    ile[punkt]++;

    M[punkt]++;

    if (M[{0,0,1}] > 0) c1 = true;
    if (punkt.a == 0 && punkt.b == 0) return;

    if (punkt.a == 0) {
        if (punkt.b < 0) {
            lewozero++;
            if (lewozero > 0 && prawozero > 0) c2 = true;
        } else {
            prawozero++;
            if (lewozero > 0 && prawozero > 0) c2 = true;
        }
    } else if ((punkt.a < 0 && punkt.S < 0) || (punkt.a > 0 && punkt.S > 0)) {
        i128 G = gcd128(punkt.a, punkt.b);
        pii128 x = {punkt.a / G, punkt.b / G};
        nad[x]++;
        if (nad[x] == 1 && pod[x] > 0) ileprostych++;
    } else {
        i128 G = gcd128(punkt.a, punkt.b);
        pii128 x = {punkt.a / G, punkt.b / G};
        x.first = -x.first;
        x.second = -x.second;
        pod[x]++;
        if (pod[x] == 1 && nad[x] > 0) ileprostych++;
    }

    if (ileprostych > 0 || (lewozero > 0 && prawozero > 0)) c2 = true;
    else c2 = false;

    dodajprosta(punkt);

    if (ilewiekszych <= 0 && proste.size() > 2) c3 = true;
    else c3 = false;
}

void usun(d punkt) {
    if (ile[punkt] > 1) {
        ile[punkt]--;
        return;
    }
    ile[punkt]--;
    M[punkt]--;
    if (M[{0,0,1}] == 0) c1 = false;
    if (punkt.a == 0 && punkt.b == 0) return;

    if (punkt.a == 0) {
        if (punkt.b < 0) {
            lewozero--;
            if (lewozero == 0 || prawozero == 0) c2 = false;
        } else {
            prawozero--;
            if (lewozero == 0 || prawozero == 0) c2 = false;
        }
    } else if ((punkt.a < 0 && punkt.S < 0) || (punkt.a > 0 && punkt.S > 0)) {
        i128 G = gcd128(punkt.a, punkt.b);
        pii128 x = {punkt.a / G, punkt.b / G};
        bool c = (pod[x] > 0 && nad[x] > 0);
        nad[x]--;
        if (c && (pod[x] == 0 || nad[x] == 0)) ileprostych--;
    } else {
        i128 G = gcd128(punkt.a, punkt.b);
        pii128 x = {punkt.a / G, punkt.b / G};
        x.first = -x.first; x.second = -x.second;
        bool c = (pod[x] > 0 && nad[x] > 0);
        pod[x]--;
        if (c && (pod[x] == 0 || nad[x] == 0)) ileprostych--;
    }

    if (ileprostych > 0 || (lewozero > 0 && prawozero > 0)) c2 = true;
    else c2 = false;

    usunprosta(punkt);

    if (ilewiekszych <= 0 && proste.size() > 2) c3 = true;
    else c3 = false;
}

// helper to safely convert small __int128 to int for printing (0..3)
int i128_to_int(i128 x) {
    long long t = (long long)x;
    return (int)t;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    // Read initial triple (use ll for reading to preserve cin behaviour)
    ll a_, b_, c_;
    if (!(cin >> a_ >> b_ >> c_)) return 0;
    i128 a = (i128)a_;
    i128 b = (i128)b_;
    i128 c = (i128)c_;

    cel = przemien(a, b, c);

    ll q;
    cin >> q;
    char x;
    int cnt = 1;
    for (ll i = 0; i < q; ++i) {
        cin >> x;
        if (x == 'A') {
            cin >> a_ >> b_ >> c_;
            i128 aa = (i128)a_;
            i128 bb = (i128)b_;
            i128 cc = (i128)c_;
            i128 TMP = gcd128(aa, gcd128(bb, cc));
            if (TMP != 0) { aa /= TMP; bb /= TMP; cc /= TMP; }
            pts[cnt] = przemien(aa, bb, cc);

            d nowy;
            nowy.a = pts[cnt].a * cel.S - cel.a * pts[cnt].S;
            nowy.b = pts[cnt].b * cel.S - cel.b * pts[cnt].S;
            nowy.S = cel.S * pts[cnt].S;
            if (nowy.a == 0 && nowy.b == 0) nowy.S = 1;
            i128 G = gcd128(nowy.a, gcd128(nowy.b, nowy.S));
            if (G != 0) { nowy.a /= G; nowy.b /= G; nowy.S /= G; }

            pts[cnt] = nowy;
            // wypisztrojke(pts[cnt]); // debug
            dodaj(pts[cnt]);
            cnt++;
        } else {
            ll idx;
            cin >> idx;
            if (idx >= 0 && idx < MAXN) {
                // debug: wypisztrojke(pts[idx]);
                usun(pts[idx]);
                pts[idx] = {0,0,0};
            } else {
                // out-of-range (shouldn't happen given original code assumptions)
            }
        }

        int out = c1 ? 1 : (c2 ? 2 : (c3 ? 3 : 0));
        cout << out << '\n';
    }

    return 0;
}

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