Submission #1263142

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263142		M_W_13	Mixture (BOI20_mixture)	C++20	60 / 100	16 ms	1652 KiB

Mixture

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define st first
#define nd second
#define pb push_back
#define wsp pair<pair<ll, ll>, ll>
const int MAXN = 1e5 + 7;
vector<wsp> vec;
vector<pair<pair<ll, ll>, int>> pom;
map <pair<ll, ll>, int> ile;
set<pair<int, int>> S;
map<int, int> jaki;
wsp T[MAXN];
int pol = 0;
int lic = 0;
ll a, b, c;

map<wsp, int> Sile;

bool dod(pair<ll, ll> p) {
    // cout << p.st << " " << p.nd << '\n';
    ile[p]++;
    if (ile[p] == 1) {
        if (ile[{-p.st, -p.nd}] >= 1) {
            pol++;
        }
    }
    if (pol > 0) {
        return true;
    }
    return false;
}

bool odejm(pair<ll, ll> p) {
    if (ile[p] == 1) {
        if (ile[{-p.st, -p.nd}] >= 1) {
            pol--;
        }
    }
    ile[p]--;
    if (pol > 0) {
        return true;
    }
    return false;
}

bool spr1() {
    if (ile[{0, 0}] > 0) {
        return true;
    }
    return false;
}

void wypisz(pair<ll, ll> p) {
    cout << p.st << " " << p.nd << " ";
}

pair<ll, ll> przemien(wsp p) {
    ll x = p.st.st;
    ll y = p.st.nd;
    ll z = p.nd;
    // cout << "x = " << x << " y = " << y << " z = " << z << '\n';
    ll X = x * c - a * z;
    ll Y = y * c - b * z;
    // if (z == 0 || Y == 0) {
        // cout << "XDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD" << '\n';
    // }
    if (z == 0) {
        X = x;
        Y = y;
    }
    ll d = __gcd(abs(X), abs(Y));
    if (d != 0) {
        X /= d;
        Y /= d;
    }
    // cout << "X = " << X << " Y = " << Y << '\n';
    return {X, Y};
}

pair<int, ld> zmiana(pair<ld, ld> p) {
    ld t1 = p.st/p.nd;
    if (p.nd == 0) {
        if (p.st < 0) {
            return {2, t1};
        }
        return {5, t1};
    }
    if (p.nd < 0) {
        if (p.st < 0) {
            return {1, t1};
        }
        return {0, t1};
    }
    if (p.st > 0) {
        return {4, t1};
    }
    return {3, t1};
}

bool por(pair<pair<ld, ld>, int> x2, pair<pair<ld, ld>, int> y2) {
    pair<ld, ld> x = x2.st;
    pair<ld, ld> y = y2.st;
    if (zmiana(x).st == zmiana(y).st) {
        __int128_t a = x.st;
        __int128_t b = x.nd;
        __int128_t c = y.st;
        __int128_t d = y.nd;
        return ((a * d) > (b * c));
    }
    return zmiana(x) > zmiana(y);
}

void przesort() {
    int sz = vec.size();
    // cout << "szzzzzzzzzzzzzzzzz = " << sz << '\n';
    rep(i, sz) {
        pom.pb({przemien(vec[i]), i});
    }
    sort(pom.begin(), pom.end(), por);
    int kt = 1;
    // cout << "SORT" << '\n';
    for (auto p: pom) {
        jaki[p.nd] = kt;
        // cout << "kt = " << kt << " ";
        pair<ll, ll> paraa = przemien(T[kt]);
        // wypisz(paraa);
        // cout << '\n';
        // ld a = paraa.st;
        // ld b = paraa.nd;
        // ld c = a/b;
        // cout << zmiana({a, b}) << '\n';
        // cout << c << '\n';
        kt++;
    }
}

bool czytak(pair<ll, ll> p1, pair<ll, ll> p2) {
    if ((p1.st * p2.nd - p2.st * p1.nd) < 0) {
        return true;
    }
    return false;
}

bool patrz(wsp p, int kt) {
    // cout << "HHH" << endl;
    int nr = jaki[kt];
    S.insert({nr, kt});
    auto it = S.upper_bound({nr, kt});
    auto it2 = S.lower_bound({nr, kt});
    // cout << "t11" << endl;
    if (it2 == S.begin()) {
        it2 = S.end();
    }
    // cout << "PR" << endl;
    it2--;
    if (it == S.end()) {
        it = S.begin();
    }
    // cout << "XDD" << endl;
    int ktlast = (*it2).nd;
    int nrlast = (*it2).st;
    int ktnxt = (*it).nd;
    int nrnxt = (*it).st;
    pair<ll, ll> plast = przemien(T[ktlast]);
    pair<ll, ll> pnxt = przemien(T[ktnxt]);
    pair<ll, ll> pter = przemien(T[kt]);
    if (czytak(plast, pnxt) || (plast == pnxt && nrlast >= nrnxt)) {
        // cout << "ODEEEEJM = ";
        // wypisz(plast);
        // wypisz(pnxt);
        // cout << '\n';
        lic--;
    }
    if (czytak(plast, pter) || (plast == pter && nrlast >= nr)) {
        // cout << "DZIAAAALAAAA = ";
        // wypisz(plast);
        // wypisz(pter);
        // cout << '\n';
        lic++;
    }
    if (czytak(pter, pnxt) || (pter == pnxt && nr >= nrnxt)) {
        // cout << "DZIAAAALAAAA = ";
        // wypisz(pter);
        // wypisz(pnxt);
        // cout << '\n';
        lic++;
    }
    if (lic == 0) {
        return true;
    }
    return false;
}

bool patrz2(wsp p, int kt) {
    int nr = jaki[kt];
    // cout << "XD" << endl;
    S.erase({nr, kt});
    // cout << "XD2" << endl;
    if ((int)S.size() == 0) {
        lic = 0;
        return false;
    }
    auto it = S.upper_bound({nr, kt});
    auto it2 = S.lower_bound({nr, kt});
    // cout << "XD3" << endl;
    if (it2 == S.begin()) {
        it2 = S.end();
    }
    it2--;
    if (it == S.end()) {
        it = S.begin();
    }
    int ktlast = (*it2).nd;
    int nrlast = (*it2).st;
    int ktnxt = (*it).nd;
    int nrnxt = (*it).st;
    pair<ll, ll> plast = przemien(T[ktlast]);
    pair<ll, ll> pnxt = przemien(T[ktnxt]);
    pair<ll, ll> pter = przemien(T[kt]);
    if (czytak(plast, pnxt) || (plast == pnxt && nrlast >= nrnxt)) {
        lic++;
    }
    if (czytak(plast, pter) || (plast == pter && nrlast >= nr)) {
        lic--;
    }
    if (czytak(pter, pnxt) || (pter == pnxt && nr >= nrnxt)) {
        lic--;
    }
    if (lic == 0) {
        return true;
    }
    return false;
}

struct upd {
    int typ;
    ll x, y, z;
};

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cout << fixed << setprecision(10);
    cin >> a >> b >> c;
    int liccccc = 0;
    while (c == 0) {
        liccccc++;
        swap(a, c);
        swap(b, c);
    }
    ll nwdd = __gcd(a, __gcd(b, c));
    a /= nwdd;
    b /= nwdd;
    c /= nwdd;
    vector<upd> zm;
    int q;
    cin >> q;
    int ktor = 0;
    rep(i, q) {
        char s;
        cin >> s;
        if (s == 'A') {
            ll x, y, z;
            cin >> x >> y >> z;
            // cout << "x = " << x << " y = " << y << " z = " << z << '\n';
            rep(cos, liccccc) {
                swap(x, z);
                swap(y, z);
            }
            nwdd = __gcd(x, __gcd(y, z));
            x /= nwdd;
            y /= nwdd;
            z /= nwdd;
            zm.pb({1, x, y, z});
            vec.pb({{x, y}, z});
            T[ktor] = {{x, y}, z};
            ktor++;
        }
        else {
            int nr;
            cin >> nr;
            nr--;
            zm.pb({2, nr, nr, nr});
        }
    }
    przesort();
    // cout << "XD" << endl;
    ktor = 0;
    rep(i, q) {
        upd now = zm[i];
        bool c1, c2, c3;
        // cout << "i = " << i << endl;
        if (now.typ == 1) {
            c2 = dod(przemien(T[ktor]));
            // cout << "REL" << endl;
            c1 = spr1();
            // cout << "FR" << endl;
            c3 = patrz(T[ktor], ktor);
            // cout << "SK" << endl;
            ktor++;
        }
        else {
            c2 = odejm(przemien(T[zm[i].x]));
            c1 = spr1();
            // cout << "FR" << endl;
            c3 = patrz2(T[zm[i].x], zm[i].x);
            // cout << "SK" << endl;
        }
        // cout << "ZIIUUUUUUUUUUUUUUUUUUUUUUUUUUUUMMM lic = " << lic << '\n';
        if (c1) {
            cout << 1 << '\n';
        }
        else if (c2) {
            cout << 2 << '\n';
        }
        else if (c3) {
            cout << 3 << '\n';
        }
        else {
            cout << 0 << '\n';
        }
    }
    return 0;
}

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