Submission #1263169

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263169		M_W_13	Mixture (BOI20_mixture)	C++20	30 / 100	5 ms	1092 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[6];
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};
}

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

void wyp(__int128_t x) {
    vector<char> vec;
    // if (x == 0) {
    //     cout << "BRRRRUUUUUUUUUUUUUUUUUHHHHHHHHH" << '\n';
    //     return ;
    // }
    while (x > 0) {
        int t = (x % 10);
        char c = t + '0';
        vec.pb(c);
        x /= 10;
    }
    reverse(vec.begin(), vec.end());
    for (auto c: vec) {
        cout << c;
    }
    cout << '\n';
}

bool por(pair<pair<ll, ll>, int> x2, pair<pair<ll, ll>, int> y2) {
    pair<ll, ll> x = x2.st;
    pair<ll, ll> y = y2.st;
    if (x2 == y2) return false;
    if (zmiana(x) == zmiana(y)) {
        // cout << "TUuuuuuuuuu = " << x.st << " " << x.nd << " " << y.st << " " << y.nd << '\n';
        bool zmien = true;
        if (x.st < 0 && x.nd > 0) {
            zmien = false;
        }
        else if (x.st > 0 && x.nd < 0) {
            zmien = false;
        }
        __int128_t a = abs(x.st);
        __int128_t b = abs(x.nd);
        __int128_t c = abs(y.st);
        __int128_t d = abs(y.nd);
        
        __int128_t w1 = a * d;
        __int128_t w2 = b * c;
        // wyp(w1);
        // wyp(w2);
        if (zmien) {
            return (w1 > w2);
        }
        return (w1 < w2);
    }
    return zmiana(x) > zmiana(y);
}

void przesort() {
    int sz = vec.size();
    // cout << "szzzzzzzzzzzzzzzzz = " << sz << '\n';
    rep(i, sz) {
        pom[zmiana(przemien(vec[i]))].pb({przemien(vec[i]), i});
    }
    for (int c2 = 5; c2 >= 0; c2--) {
        sort(pom[c2].begin(), pom[c2].end(), por);
    }
    int kt = 1;
    // cout << "SORT" << '\n';
    for (int c2 = 5; c2 >= 0; c2--) {
        for (auto p: pom[c2]) {
            jaki[p.nd] = kt;
            // cout << "kt = " << kt << " ";
            // pair<ll, ll> paraa = przemien(T[p.nd]);
            // wypisz(paraa);
            // cout << '\n';
            // ld a = paraa.st;
            // ld b = paraa.nd;
            // ld c = a/b;
            // cout << zmiana(paraa) << '\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: 0 / 30
• Subtask 4: 0 / 40