Submission #1262747

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262747		M_W_13	Mixture (BOI20_mixture)	C++20	0 / 100	0 ms	324 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;
ld INF = 1e15;
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) {
    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) {
    ile[p]--;
    if (ile[p] == 0) {
        if (ile[{-p.st, -p.nd}] >= 1) {
            pol--;
        }
    }
    if (pol > 0) {
        return true;
    }
    return false;
}

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

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

bool por(pair<pair<ll, ll>, int> x2, pair<pair<ll, ll>, int> y2) {
    pair<ld, ld> x = x2.st;
    pair<ld, ld> y = y2.st;
    ld t1 = x.st/x.nd;
    if (x.st < 0) {
        t1 -= (INF);
    }
    ld t2 = y.st/y.nd;
    if (y.st < 0) {
        t2 -= (INF);
    }
    return (t1 > t2);
}

void przesort() {
    int sz = vec.size();
    rep(i, sz) {
        pom.pb({przemien(vec[i]), i});
    }
    sort(pom.begin(), pom.end(), por);
    int kt = 1;
    for (auto p: pom) {
        jaki[p.nd] = kt;
        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)) {
        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;
}

bool patrz2(wsp p, int kt) {
    int nr = jaki[kt];
    S.erase({nr, kt});
    auto it = S.upper_bound({nr, kt});
    auto it2 = S.lower_bound({nr, kt});
    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);
    cin >> a >> b >> c;
    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;
            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();
            c3 = patrz2(T[zm[i].x], zm[i].x);
        }
        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: 0 / 13
• Subtask 2: 0 / 17
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40