Submission #256561

#	Time	Username	Problem	Language	Result	Execution time	Memory
256561		davitmarg	Mixture (BOI20_mixture)	C++17	30 / 100	23 ms	768 KiB

Mixture

/*
DavitMarg
In a honky-tonk,
Down in Mexico
*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#include <fstream>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(), v.end()
#define fastIO ios::sync_with_stdio(false); cin.tie(0)
using namespace std;

const int N = 200005;

LD X, Y, Z, pi = 3.1415926535897932384626433832795028841971, eps = 10e-15;
vector<LD> vx, vy;
multiset<pair<LD, LD>> s;
multiset<LD> sa, mx;
int n, ans2;

LD getAng(LD x, LD y)
{
    LD d = sqrtl(x * x + y * y);
    LD e = acos(x / d);
    assert(d != 0);
    if (y < 0)
        e = pi + pi - e;
    return e;
}

LD inv(LD e)
{
    if (e >= pi)
        return e - pi;
    return e + pi;
}

bool fnd(LD e)
{
    auto it = sa.lower_bound(e - eps);
    return (it != sa.end() && *it <= e + eps);
}

void add(LD e)
{
    sa.insert(e);
    if (sa.size() == 1)
        return;
    auto it = sa.find(e);

    LD lst, nxt;

    if (it == sa.begin())
    {
        ++it;
        mx.insert(*it - e);
        return;
    }
    else
    {
        it--;
        lst = *it;
        it++;
    }
    it++;

    if (it == sa.end())
    {
        it--;
        it--;
        mx.insert(e - *it);
        return;
    }
    else
        nxt = *it;
    mx.erase(mx.lower_bound(abs(nxt - lst) - eps));
    mx.insert(abs(e - lst));
    mx.insert(abs(e - nxt));
}


void rem(LD e)
{

    if (sa.size() == 1)
    {
        sa.clear();
        return;
    }
    auto it = sa.upper_bound(e - eps);
    e = *it;

    LD lst, nxt;

    if (it == sa.begin())
    {
        ++it;
        mx.erase(mx.lower_bound(*it - e - eps));
        sa.erase(sa.find(e));
        return;
    }
    else
    {
        it--;
        lst = *it;
        it++;
    }
    it++;

    if (it == sa.end())
    {
        it--;
        mx.erase(mx.lower_bound(e - *it - eps));
        sa.erase(sa.find(e));
        return;
    }
    else
        nxt = *it;
    mx.insert(abs(nxt - lst));
    mx.erase(mx.lower_bound(e - lst - eps));
    mx.erase(mx.lower_bound(nxt - e - eps));
    sa.erase(sa.find(e));
}

LD get()
{
    if (mx.empty())
        return pi + pi;
    LD res = 0;
    if (sa.size() > 1)
    {
        LD e = (*sa.rbegin() - *sa.begin());
        res = pi + pi - e;
    }
    return max(res, *mx.rbegin());
}

void add(LD x, LD y)
{
    s.insert(MP(x, y));
    if (abs(x) > eps || abs(y) > eps)
    {
        LD e = getAng(x, y);
        if (!fnd(e) && fnd(inv(e)))
            ans2++;
        add(e);
    }
}


void rem(LD x, LD y)
{
    s.erase(s.find(MP(x, y)));
    if (abs(x) > eps || abs(y) > eps)
    {
        LD e = getAng(x, y);
        rem(e);
        if (!fnd(e) && fnd(inv(e)))
            ans2--;
    }
}

int main()
{
    fastIO;
    cin >> Z >> Y >> X;
    Z += X + Y;
    cin >> n;
    /*X /= Z;
    Y /= Z;*/
    vx.push_back(0);
    vy.push_back(0);
    while (n--)
    {
        char c;
        cin >> c;
        if (c == 'A')
        {
            LD x, y, z;
            cin >> z >> y >> x;
            z += x + y;
            x *= Z / z;
            y *= Z / z;
            x -= X;
            y -= Y;
            if (sqrtl(x*x+y*y) <= eps)
            {
                x = 0;
                y = 0;
            }
            vx.push_back(x);
            vy.push_back(y);
            add(x, y);
        }
        else
        {
            int p;
            cin >> p;
            rem(vx[p], vy[p]);
        }

        if (s.find(MP(0, 0)) != s.end())
            cout << 1 << endl;
        else if (ans2)
            cout << 2 << endl;
        else if (get() <= pi + eps)
            cout << 3 << endl;
        else
            cout << 0 << endl;
    }

    return 0;
}

/*


*/

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