Submission #1302135

#	Time	Username	Problem	Language	Result	Execution time	Memory
1302135		otarius	Mixture (BOI20_mixture)	C++20	100 / 100	246 ms	26480 KiB

Mixture

#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace __gnu_pbds;
using namespace std;

// #pragma GCC optimize("Ofast")
// #pragma GCC optimize ("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#define ff first
#define sc second
#define pb push_back
#define ll long long
#define pll pair<ll, ll>
#define pii pair<int, int>
#define ull unsigned long long
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rngl(chrono::steady_clock::now().time_since_epoch().count());

// #define int long long
// #define int unsigned long long

// #define ordered_set(T) tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>
// #define ordered_multiset(T) tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>

// const ll mod = 1e9 + 7;
// const ll mod = 998244353;

const ll inf = 1e9;
const ll biginf = 1e18;
const int maxN = 1e5 + 15;

int n, cur;
ll s[maxN], p[maxN], g[maxN];
bool isgood(int i, int j) {
    __int128 sumi = s[i] + p[i] + g[i];
    __int128 sumj = s[j] + p[j] + g[j];
    return (s[i] * sumj == s[j] * sumi && p[i] * sumj == p[j] * sumi);
}
struct pt {
    int cnt = 0;
    void insert(int i) {
        cnt += isgood(i, 0);
    }

    void erase(int i) {
        cnt -= isgood(i, 0);
    }

    bool check() {
        return (cnt > 0);
    }
} dt1;

struct seg {
    ll cnt = 0;
    map<pll, ll> mp;
    void insert(int i) {
        __int128 dx = (__int128)s[i] * (s[0] + p[0] + g[0]) - (__int128)s[0] * (s[i] + p[i] + g[i]);
        __int128 dy = (__int128)p[i] * (s[0] + p[0] + g[0]) - (__int128)p[0] * (s[i] + p[i] + g[i]);
        if (dx == 0 && dy == 0) return;

        __int128 g = __gcd(abs((ll)dx), abs((ll)dy));
        dx /= g; dy /= g;

        cnt += mp[{-dx, -dy}]; mp[{dx, dy}]++;
    }

    void erase(int i) {
        __int128 dx = (__int128)s[i] * (s[0] + p[0] + g[0]) - (__int128)s[0] * (s[i] + p[i] + g[i]);
        __int128 dy = (__int128)p[i] * (s[0] + p[0] + g[0]) - (__int128)p[0] * (s[i] + p[i] + g[i]);
        if (dx == 0 && dy == 0) return;

        __int128 g = __gcd(abs((ll)dx), abs((ll)dy));
        dx /= g; dy /= g;

        cnt -= mp[{-dx, -dy}]; mp[{dx, dy}]--;
    }

    bool check() {
        return (cnt > 0);
    }
} dt2;


struct tri {
    struct comp {
        bool operator()(const pair<__int128, __int128>& a, const pair<__int128, __int128>& b) const {
            bool x = (a.sc > 0 || (a.sc == 0 && a.ff > 0));
            bool y = (b.sc > 0 || (b.sc == 0 && b.ff > 0));
            if (x != y) return (x > y);
            return (a.ff * b.sc - a.sc * b.ff > 0);
        }
    };

    set<pair<__int128, __int128>, comp> dir;
    map<pair<__int128, __int128>, int, comp> mp;
    int cnt = 0;

    __int128 cross(pair<__int128, __int128> a, pair<__int128, __int128> b) {
        return a.ff * b.sc - a.sc * b.ff;
    }

    void insert(int i) {
        __int128 dx = (__int128)s[i] * (s[0] + p[0] + g[0]) - (__int128)s[0] * (s[i] + p[i] + g[i]);
        __int128 dy = (__int128)p[i] * (s[0] + p[0] + g[0]) - (__int128)p[0] * (s[i] + p[i] + g[i]);
        if (dx == 0 && dy == 0) return;

        __int128 g = __gcd(abs((ll)dx), abs((ll)dy));
        dx /= g; dy /= g;
        
        auto it1 = mp.find({dx, dy});
        if (it1 != mp.end()) {
            it1 -> sc++; return;
        }

        if (dir.empty()) {
            dir.insert({dx, dy}); mp[{dx, dy}] = 1; return;
        }

        auto it = dir.insert({dx, dy}).ff; mp[{dx, dy}] = 1;
        if (dir.size() == 2) {
            auto prv = (it == dir.begin() ? prev(dir.end()) : prev(it));
            auto nxt = next(it); if (nxt == dir.end()) nxt = dir.begin();

            if (cross(*prv, *it) <= 0) cnt++;
            if (cross(*it, *nxt) <= 0) cnt++;

            return;
        }

        auto prv = (it == dir.begin() ? prev(dir.end()) : prev(it));
        auto nxt = next(it); if (nxt == dir.end()) nxt = dir.begin();

        if (cross(*prv, *nxt) <= 0) cnt--;
        if (cross(*prv, *it) <= 0) cnt++;
        if (cross(*it, *nxt) <= 0) cnt++;
    }

    void erase(int i) {
        __int128 dx = (__int128)s[i] * (s[0] + p[0] + g[0]) - (__int128)s[0] * (s[i] + p[i] + g[i]);
        __int128 dy = (__int128)p[i] * (s[0] + p[0] + g[0]) - (__int128)p[0] * (s[i] + p[i] + g[i]);
        if (dx == 0 && dy == 0) return;

        __int128 g = __gcd(abs((ll)dx), abs((ll)dy));
        dx /= g; dy /= g;

        auto it1 = mp.find({dx, dy});
        if (it1 == mp.end()) return;
        if (it1 -> sc > 1) {
            it1 -> sc--; return;
        }

        auto it = dir.find({dx, dy});
        if (it == dir.end()) {
            mp.erase(it1); return;
        }

        if (dir.size() == 1) {
            dir.erase(it); mp.erase(it1); return;
        }

        if (dir.size() == 2) {
            auto prv = (it == dir.begin() ? prev(dir.end()) : prev(it));
            auto nxt = next(it); if (nxt == dir.end()) nxt = dir.begin();

            if (cross(*prv, *it) <= 0) cnt--;
            if (cross(*it, *nxt) <= 0) cnt--;

            dir.erase(it); mp.erase(it1);
            return;
        }

        auto prv = (it == dir.begin() ? prev(dir.end()) : prev(it));
        auto nxt = next(it); if (nxt == dir.end()) nxt = dir.begin();

        if (cross(*prv, *nxt) <= 0) cnt++;
        if (cross(*prv, *it) <= 0) cnt--;
        if (cross(*it, *nxt) <= 0) cnt--;

        dir.erase(it); mp.erase(it1);
    }

    bool check() {
        if (dir.size() < 3) return 0;
        return (cnt == 0);
    }
} dt3;

void solve() {
    cin >> s[0] >> p[0] >> g[0] >> n;
    while (n--) {
        char c; cin >> c;
        if (c == 'A') {
            ++cur; cin >> s[cur] >> p[cur] >> g[cur];
            dt1.insert(cur); dt2.insert(cur); dt3.insert(cur);
        } else {
            int pos; cin >> pos;
            dt1.erase(pos); dt2.erase(pos); dt3.erase(pos);
        }

        if (dt1.check()) cout << "1\n";
        else if (dt2.check()) cout << "2\n";
        else if (dt3.check()) cout << "3\n";
        else cout << "0\n";
    }
}
int32_t main() { 
// #ifndef ONLINE_JUDGE
//     freopen("input.txt", "r", stdin);
//     freopen("output.txt", "w", stdout);
// #endif
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
        // cout << '\n';
    }
    return 0;
}

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