Submission #1263296

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

Mixture

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

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


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

d pts[MAXN];
d cel;

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

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, ll, comp> M;
map<pii, ll> nad;
map<pii, ll> pod;
ll lewozero = 0;
ll prawozero = 0;
ll ilewiekszych = 0;
ll ileprostych = 0;

ll wypuklosc(const d &d1, const d &d2, const d &d3){
    ll v = d3.a * d1.b - d1.a * d3.b;
    if(v < 0) return -1;
    else if(v > 0) return 1;
    return 0;
}


struct comp2{
    bool operator()(const d &u, const d &v) const {
        int hu = (u.b > 0 || (u.b == 0 && u.a > 0)) ? 0 : 1;
        int hv = (v.b > 0 || (v.b == 0 && v.a > 0)) ? 0 : 1;
        if (hu != hv) return hu < hv;
        __int128 cr = (__int128)u.a * v.b - (__int128)u.b * v.a;
        if (cr != 0) return cr > 0;
        if (u.a != v.a) return u.a < v.a;
        if (u.b != v.b) return u.b < v.b;
        return u.S < v.S;
    }
};




multiset<d, comp2> proste;

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


void dodajprosta(d punkt){
    proste.insert(punkt);
    if(proste.size() < 3){
        ilewiekszych = proste.size();
        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();
    if(wypuklosc(*prev, {0, 0, 1}, *nxt) == -1) ilewiekszych--;
    if(wypuklosc(*prev, {0, 0, 1}, punkt) == -1) ilewiekszych++;
    if(wypuklosc(punkt, {0, 0, 1}, *nxt) == -1) ilewiekszych++;
    return;
}

void usunprosta(d punkt){
    auto x = proste.find(punkt);
    if(proste.size() <= 3){
        ilewiekszych = proste.size() - 1;
        auto it = proste.find(punkt);
        if(it != proste.end()) proste.erase(it);
        return;
    }
    auto prev = x;
    if(prev == proste.begin()){
        prev = --(proste.end());
    }
    else{
        prev--;
    }
    auto nxt = x;
    nxt++;
    if(nxt == proste.end()) nxt = proste.begin();

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

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

ll gcd(ll a, ll b){
    return __gcd(llabs(a), llabs(b));
}

void dodaj(d punkt){
    // ans = 1
    M[punkt]++; 
    if(M[{0,0,1}] > 0) c1 = true;
    if(punkt.a == 0 and punkt.b == 0) return;

    //ans = 2
    //cout << punkt.a << " " << punkt.b << " " << punkt.S << " P\n";
    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)){
        ll G = gcd(punkt.a, punkt.b);
        pii x = {punkt.a/G,punkt.b/G};
        //cout << x.first << " " << x.second << " X\n";
        nad[x]++;
        if(pod[x] > 0) ileprostych++;
    }
    else{
        ll 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(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() != 0) c3 = true;
    else c3 = false;
}

void usun(d 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)){
        ll 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{
        ll G = gcd(punkt.a, punkt.b);
        pii x = {punkt.a/G,punkt.b/G};
        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() != 0) c3 = true;
    else c3 = false;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll a, b, c;
    cin >> a >> b >> c;
    cel = przemien(a, b, c);
    ll q;
    cin >> q;
    char x;
    for(ll i = 0; i < q; ++i){
        cin >> x;
        if(x == 'A'){
            cin >> a >> b >> c;
            pts[i+1] = przemien(a, b, c);
            d nowy = {pts[i+1].a * cel.S - cel.a * pts[i+1].S, pts[i+1].b * cel.S - cel.b * pts[i+1].S, cel.S * pts[i+1].S};
            if(nowy.a == 0 and nowy.b == 0) nowy.S = 1;
            ll G = gcd(nowy.a, gcd(nowy.b, nowy.S));
            nowy.a /= G;
            nowy.b /= G;
            nowy.S /= G;
            pts[i + 1] = nowy;
            dodaj(pts[i+1]);
        }
        else{
            cin >> a;
            usun(pts[a]);
            pts[a] = {0, 0, 0};
        }
        cout << (c1 ? 1 : (c2 ? 2 : (c3 ? 3 : 0))) << "\n";
    }
    return 0;
}

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