Submission #1166649

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166649		Math4Life2020	Mixture (BOI20_mixture)	C++20	100 / 100	142 ms	14096 KiB

Mixture

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

pii tfm(pii p1) {
    if (p1.first==0 && p1.second==0) {
        return p1;
    }
    ll g = gcd(p1.first,p1.second);
    return {p1.first/g,p1.second/g};
}

pii neg(pii p1) {
    return {-p1.first,-p1.second};
}

ll num0 = 0; //(0,0)
ll nump = 0; //(1,0)
ll numn = 0; //(-1,0)
multiset<ld> mt; //multiset top (y>0): x/y
multiset<ld> mb; //multiset bottom (y<0): x/y
ll pairc = 0; //pair count: how many pairs have positive value (mpair)?
map<pii,pii> mpair; //EXCLUDE y=0; (pair version with positive y) -> {# of that, # of opp}

void insrt(pii p0) {
    ll x = p0.first; ll y = p0.second;
    if (y==0) {
        if (x==0) {
            num0++;
        } 
        if (x>0) {
            nump++;
        }
        if (x<0) {
            numn++;
        }
        return;
    }
    if (y>0) {
        if (mpair.find({x,y})==mpair.end()) {
            mpair[{x,y}]={1,0};
        } else {
            pii pc = mpair[{x,y}];
            mpair[{x,y}]={pc.first+1,pc.second};
            if (pc.first==0 && pc.second>=1) {
                pairc++;
            }
        }
        mt.insert(((ld)x)/y);
    }
    if (y<0) {
        if (mpair.find({-x,-y})==mpair.end()) {
            mpair[{-x,-y}]={0,1};
        } else {
            pii pc = mpair[{-x,-y}];
            mpair[{-x,-y}]={pc.first,pc.second+1};
            if (pc.first>=1 && pc.second==0) {
                pairc++;
            }
        }
        mb.insert(((ld)x)/y);
    }
}

void del(pii p0) {
    ll x = p0.first; ll y = p0.second;
    if (y==0) {
        if (x==0) {
            num0--;
        } 
        if (x>0) {
            nump--;
        }
        if (x<0) {
            numn--;
        }
        return;
    }
    if (y>0) {
        pii pc = mpair[{x,y}];
        mpair[{x,y}]={pc.first-1,pc.second};
        if (pc.first==1 && pc.second>=1) {
            pairc--;
        }
        mt.erase(mt.find(((ld)x)/y));
    }
    if (y<0) {
        pii pc = mpair[{-x,-y}];
        mpair[{-x,-y}]={pc.first,pc.second-1};
        if (pc.first>=1 && pc.second==1) {
            pairc--;
        }
        mb.erase(mb.find((((ld)x)/y)));
    }
}

bool qry() { //exists triangle?
    if (nump>0 && numn>0) {
        assert(0);
    }
    if (mt.size()==0 || mb.size()==0) {
        return 0;
    }
    ld minb = *(mb.begin()); //x/y for y<0
    ld maxb = *(--mb.end());
    ld mint = *(mt.begin());
    ld maxt = *(--mt.end());
    if (nump>0) {
        if (maxb>mint) {
            return 1;
        }
    }
    if (numn>0) {
        if (maxt>minb) {
            return 1;
        }
    }
    if (maxb>mint && maxt>minb) {
        return 1;
    }
    return 0;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
    ll A,B,C,T; cin >> A >> B >> C; T=A+B+C;
    ll N; cin >> N;
    vector<array<ll,3>> acur;
    for (ll i=0;i<N;i++) {
        string S; cin >> S;
        if (S[0]=='A') {
            ll a1,b1,c1; cin >> a1 >> b1 >> c1; ll t1 = a1+b1+c1;
            acur.push_back({a1,b1,c1});
            insrt(tfm({T*a1-t1*A,T*b1-t1*B}));
        } else {
            ll r; cin >> r;
            r--;
            auto A1 = acur[r];
            ll a1 = A1[0]; ll b1 = A1[1]; ll c1 = A1[2]; ll t1 = a1+b1+c1;
            del(tfm({T*a1-t1*A,T*b1-t1*B}));
        }
        if (num0>0) {
            cout << "1\n";
        } else if (pairc>0 || (numn>0 && nump>0)) {
            cout << "2\n";
        } else if (qry()) {
            cout << "3\n";
        } else {
            cout << "0\n";
        }
    }
}

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