Submission #1263390

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263390		niepamietamhasla	Mixture (BOI20_mixture)	C++20	0 / 100	0 ms	320 KiB

Mixture

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<__int128,__int128>
#define ld long double
#define i128 = __int128;

const ll INF = 2e9;
const ll MAXN = 1e5 + 5;


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

d pts[MAXN];
d cel;

d przemien(__int128 a, __int128 b, __int128 c){
    __int128 S = a + b + c;
    __int128 G = gcd(a, gcd(b, S));
    return {a/G, b/G, S/G};
}


void wypisztrojke(d u){
    //cout << "(" << (ld)(1.00 * u.b / u.S) << ", " << (ld)(1.00 * u.a / u.S) << ")   para\n";
    //cout << 1.00 * u.b / u.a << " A przez B\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;
    }
};

map<d, int, comp> ile;
map<d, ll, comp> M;
map<pii, ll> nad;
map<pii, ll> pod;
ll lewozero = 0;
ll prawozero = 0;
ll ilewiekszych = 0;
ll ileprostych = 0;

__int128 wypuklosc(const d &d1, const d &d2, const d &d3){
    // cout << d1.a << " " << d1.b << "\n";
    // cout << d3.a << " " << d3.b << "\n";
    __int128 v = +d3.a * d1.b - d1.a * d3.b;
    //cout << v << " wyp\n";
    if (v < 0) return -1;
    else if(v > 0) return 1;
    else return 0;
}
struct comp2 {
    bool operator()(const d &d1, const d &d2) const {
        bool up1 = (d1.a > 0) or (d1.a == 0 and d1.b > 0);
        bool up2 = (d2.a > 0) or (d2.a == 0 and d2.b > 0);
        if (up1 != up2) return up1; 

        __int128 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;


__int128 wypuklosc2(const d &d1, const d &d2, const d &d3){
    //cout << d1.a << " " << d1.b << " " << d1.S << "\n";
    //cout << d3.a << " " << d3.b << "\n";   
    __int128 v = +d3.a * d1.b - d1.a * d3.b;
    //cout << v << "\n";  
    //cout << v << " wyp\n";
    if (v < 0) return -1;
    else if(v > 0) return 1;

    if(d1.a == 0 and d3.a == 0) return 1;
    if((d1.a > 0 and d3.a < 0) or (d1.a < 0 and 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--;
    }
    // wypisztrojke(*prev);
    // wypisztrojke(punkt);
    // wypisztrojke(*nxt);
    //cout << ilewiekszych << " przed\n";
    if(wypuklosc2(*prev, {0, 0, 1}, *nxt) == -1) {
        //cout << "#\n";
        ilewiekszych--;
    }
    // wypisztrojke(punkt);
    // cout << "DODANA\n";
    proste.insert(punkt);

    if(wypuklosc2(*prev, {0, 0, 1}, punkt) == -1) ilewiekszych++;
    if(wypuklosc2(punkt, {0, 0, 1}, *nxt) == -1) ilewiekszych++;
    //cout << ilewiekszych << " po\n";
    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);
    auto prev = x;
    if(prev == proste.begin()){
        prev = --(proste.end());
    }
    else{
        prev--;
    }
    auto nxt = x;
    nxt++;
    if(nxt == proste.end()) nxt = proste.begin();


    // wypisztrojke(*prev);
    // wypisztrojke(*x);
    // wypisztrojke(*nxt);

    //cout << ilewiekszych << " przed\n";
    if(wypuklosc2(*prev, {0, 0, 1}, punkt) == -1) ilewiekszych--;
    //cout << ilewiekszych <<  " XD\n";
    if(wypuklosc2(punkt, {0, 0, 1}, *nxt) == -1) ilewiekszych--;

    //cout << ilewiekszych << " po\n";
    auto it = proste.find(punkt);
    if(it != proste.end()) proste.erase(it);

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

    return;
}

__int128 gcd(__int128 a, __int128 b){
    return __gcd(abs(a), abs(b));
}

void dodaj(d punkt){
    //cout << punkt.a << " " << punkt.b << " " << punkt.S << " P\n";
    if(ile[punkt] > 0){
        //cout << "juz istnieje\n";
        ile[punkt]++;
        return;
    }
    ile[punkt]++;
    // ans = 1
    M[punkt]++; 
    if(M[{0,0,1}] > 0) c1 = true;
    if(punkt.a == 0 and punkt.b == 0) return;

    //ans = 2
    //wypisztrojke(punkt);
    if(punkt.a == 0){
        if(punkt.b < 0){
            lewozero++;
            if(lewozero > 0 and prawozero > 0) c2 = true;
        }
        else{
            prawozero++;
            if(lewozero > 0 and prawozero > 0) c2 = true;
        }
    }
    else if((punkt.a < 0 and punkt.S < 0) or (punkt.a > 0 and punkt.S > 0)){
        __int128 G = gcd(punkt.a, punkt.b);
        pii x = {punkt.a/G,punkt.b/G};
        //cout << x.first << " " << x.second << " X\n";
        nad[x]++;
        if(nad[x] == 1 and pod[x] > 0) ileprostych++;
    }
    else{
        __int128 G = gcd(punkt.a, punkt.b);
        pii x = {punkt.a/G,punkt.b/G};
        //cout << x.first << " " << x.second << " X\n";
        x.first *= -1;
        x.second *= -1;
        pod[x]++;
        if(pod[x] == 1 and nad[x] > 0) ileprostych++;
    }
    if(ileprostych > 0 or (lewozero > 0 and prawozero > 0)) c2 = true;
    else c2 = false;
    

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

void usun(d punkt){
    if(ile[punkt] > 1){
        //cout << "wiecej niz jedna\n";
        ile[punkt]--;
        return;
    }
    ile[punkt]--;
    M[punkt]--;
    if(M[{0,0,1}] == 0) c1 = false;
    if(punkt.a == 0 and punkt.b == 0) return;
    
    //ans = 2
    if(punkt.a == 0){
        if(punkt.b < 0){
            lewozero--;
            if(lewozero == 0 or prawozero == 0) c2 = false;
        }
        else{
            prawozero--;
            if(lewozero == 0 or prawozero == 0) c2 = false;
        }
    }
    else if((punkt.a < 0 and punkt.S < 0) or (punkt.a > 0 and punkt.S > 0)){
        __int128 G = gcd(punkt.a, punkt.b);
        pii x = {punkt.a/G,punkt.b/G};
        bool c = (pod[x] > 0 and nad[x] > 0);
        nad[x]--;
        if(c and (pod[x] == 0 or nad[x] == 0)) ileprostych--;
    }
    else{
        __int128 G = gcd(punkt.a, punkt.b);
        pii x = {punkt.a/G,punkt.b/G};
        x.first *= -1;
        x.second *= -1;
        bool c = (pod[x] > 0 and nad[x] > 0);
        pod[x]--;
        if(c and (pod[x] == 0 or nad[x] == 0)) ileprostych--;
    }
    if(ileprostych > 0 or (lewozero > 0 and prawozero > 0)) c2 = true;
    else c2 = false;

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

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    __int128 a, b, c;
    cel = przemien(a, b, c);
    ll x, y, z;
    cin >> x >> y >> z;
    a = x;
    b = y;
    c = z;
    cel = przemien(a, b, c);
    ll q;
    cin >> q;
    char T;
    int cnt = 1;
    for(ll i = 0; i < q; ++i){
        //if(i == 4) break;
        cin >> T;
        if(T == 'A'){
            cin >> x >> y >> z;
            a = x;
            b = y;
            c = z;
            __int128 TMP = gcd(a, gcd(b, c));
            a /= TMP;
            b /= TMP;
            c /= TMP;
            pts[cnt] = przemien(a, b, c);
            d nowy = {pts[cnt].a * cel.S - cel.a * pts[cnt].S, pts[cnt].b * cel.S - cel.b * pts[cnt].S, cel.S * pts[cnt].S};
            if(nowy.a == 0 and nowy.b == 0) nowy.S = 1;
            __int128 G = gcd(nowy.a, gcd(nowy.b, nowy.S));
            nowy.a /= G;
            nowy.b /= G;
            nowy.S /= G;
            //cout << nowy.a << " " << nowy.b << " " << nowy.S << " punkt\n";
            pts[cnt] = nowy;
            wypisztrojke(pts[cnt]);
            //cout << "NOWAAAA\n";
            dodaj(pts[cnt]);
            cnt++;
        }
        else{
            // cout << wypuklosc(pts[1], {0, 0, 1}, pts[2]) << " wyp\n";
            cin >> x;
            a = x;
            //cout << pts[a].a << " " << pts[a].b << " " << pts[a].S << " ptsA\n";
            wypisztrojke(pts[a]);
            //cout << "del\n";
            usun(pts[a]);
            pts[a] = {0, 0, 0};
        }
        // cout << "\n";
        // cout << "start punktow\n";
        // for(auto u : proste){
        //     wypisztrojke(u);
        // }
        // cout << "koniec punktow\n";
        // cout << "\n";
        cout << (c1 ? 1 : (c2 ? 2 : (c3 ? 3 : 0))) << "\n";
        //cout << ilewiekszych << " ILE WIEKSZYCH\n";
        //cout << proste.size() << " sssssssssssssssssssajz\n";
    }
    return 0;
}

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