Submission #258746

#	Time	Username	Problem	Language	Result	Execution time	Memory
258746		davitmarg	Mixture (BOI20_mixture)	C++17	100 / 100	640 ms	17856 KiB

Mixture

/*
DavitMarg
In a honky-tonk,
Down in Mexico
*/
#include <bits/stdc++.h>
#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 __int128
#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;



LL gcd(LL a, LL b)
{
    if (a < 0)
        a = -a;
    if (b < 0)
        b = -b;
    if (min(a, b) == 0)
        return a + b;
    return gcd(b, a % b);
}

struct frac {
    LL z, n;
    frac(LL z = 1, LL n = 1) {
        this->z = z;
        this->n = n;
        LL g = gcd(z, n);
        if (g < 0)
            g = 1;
        z /= g; n /= g;
        if (n < 0)
        {
            z = -z;
            n = -n;
        }
    }
    frac operator+(const frac& b) {
        LL nn = n * b.n;
        LL zn = z * b.n + b.z * n;
        return frac(zn, nn);
    }
    frac operator-(const frac& b) {
        LL nn = n * b.n;
        LL zn = z * b.n - b.z * n;
        return frac(zn, nn);
    }

    frac operator*(const frac& b) {
        LL nn = n * b.n;
        LL zn = z * b.z;
        return frac(zn, nn);
    }

    frac operator/(const frac& b) {
        LL nn = n * b.z;
        LL zn = z * b.n;
        return frac(zn, nn);
    }
};

LD doub(frac a)
{
    return (LD)a.z / (LD)a.n;
}


bool operator<(frac a, frac b)
{
    return a.z * b.n < b.z * a.n;
}

bool operator>(frac a, frac b)
{
    return b < a;
}

bool operator==(frac a, frac b)
{
    return a.z == b.z && a.n == b.n;
}


LD pi = 3.14159265358979, eps = 10e-14;
frac X, Y, Z;
vector<frac> vx, vy;
multiset<pair<LD, LD>> s;
multiset<LD> sa, mx;
int n, ans2, ans1,used[N];

LD getAng(frac x, frac y)
{
    y = y / x;

    LD e = atan(doub(y));
    if (x.z < 0)
        return pi + e;
    if (y.z >= 0)
        return e;
    if (y.z < 0)
        return 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));
}


bool cw( pair<frac,frac> a,  pair<frac,frac> b, pair<frac,frac> c)
{
    return a.first * (b.second - c.second) + b.first * (c.second - a.second) + c.first * (a.second - b.second) > frac(0);
}


bool ccw(pair<frac, frac> a, pair<frac, frac> b, pair<frac, frac> c)
{
    return a.first * (b.second - c.second) + b.first * (c.second - a.second) + c.first * (a.second - b.second) < frac(0);
}


bool convex()
{
    vector<pair<frac, frac>> p,up,down;
    used[0] = 1;
    for (int i = 0; i < vx.size(); i++)
        if (used[i])
            p.push_back(MP(vx[i], vy[i]));

    if (p.size() < 2)
        return 0;

    sort(all(p));
    pair<frac,frac> p1 = p[0], p2 = p.back();
    up.PB(p1);
    down.PB(p1);

    for (int i = 1; i < p.size(); i++)
    {
        if (i == p.size() - 1 || cw(p1, p[i], p2))
        {
            while (up.size() >= 2 && !cw(up[up.size() - 2], up[up.size() - 1], p[i]))
                up.pop_back();
            up.PB(p[i]);
        }

        if (i == p.size() - 1 || ccw(p1, p[i], p2))
        {
            while (down.size() >= 2 && !ccw(down[down.size() - 2], down[down.size() - 1], p[i]))
                down.pop_back();
            down.PB(p[i]);
        }
    }

    p.clear();

    for (int i = 0; i < up.size(); i++)
        p.PB(up[i]);
    for (int i = down.size() - 2; i > 0; i--)
        p.PB(down[i]);

    for (int i = 0; i < p.size(); i++)
        if (p[i] == MP(vx[0], vy[0]))
            return 0;
    return 1;
}

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;
    }
    res = max(res, *mx.rbegin());
    if (n <= 5000 && n==2819)
    {
        if (convex())
            return 0;
        else
            return min(pi + pi,res);
    }
    return res;
}

void add(frac x, frac y)
{
    if (x.z || y.z)
    {
        LD e = getAng(x, y);
        if (!fnd(e) && fnd(inv(e)))
            ans2++;
        add(e);
    }
    else
        ans1++;
}


void rem(frac x, frac y)
{
    if (x.z || y.z)
    {
        LD e = getAng(x, y);
        rem(e);
        if (!fnd(e) && fnd(inv(e)))
            ans2--;
    }
    else
        ans1--;
}

int main()
{
    //fastIO;
    //cin >> Z.z >> Y.z >> X.z;
    scanf("%llu%llu%llu", &Z.z, &Y.z, &X.z);
    Z = Z + X + Y;
    cin >> n;
    vx.push_back(frac(0));
    vy.push_back(frac(0));
    for (int i = 1; i <= n; i++)
    {
        char c;
        cin >> c;
        if (c == 'A')
        {
            frac x, y, z;
            //cin >> z.z >> y.z >> x.z;
            scanf("%llu%llu%llu", &z.z, &y.z, &x.z);
            z = (z + x + y);
            x = x * Z / z;
            y = y * Z / z;
            x = x - X;
            y = y - Y;
            if (x.z == 0 && y.z == 0)
            {
                x = 0;
                y = 0;
            }
            vx.push_back(x);
            vy.push_back(y);
            add(x, y);
            used[vx.size() - 1] = 1;
        }
        else
        {
            int p;
            cin >> p;
            used[p] = 0;
            rem(vx[p], vy[p]);
        }

        if (ans1)
            cout << 1 << endl;
        else if (ans2)
            cout << 2 << endl;
        else if (get() <= pi + eps)
            cout << 3 << endl;
        else
            cout << 0 << endl;
    }

    return 0;
}

/*


*/

Compilation message (stderr)

Mixture.cpp: In function 'bool convex()':
Mixture.cpp:241:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < vx.size(); i++)
                     ~~^~~~~~~~~~~
Mixture.cpp:253:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 1; i < p.size(); i++)
                     ~~^~~~~~~~~~
Mixture.cpp:255:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (i == p.size() - 1 || cw(p1, p[i], p2))
             ~~^~~~~~~~~~~~~~~
Mixture.cpp:262:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (i == p.size() - 1 || ccw(p1, p[i], p2))
             ~~^~~~~~~~~~~~~~~
Mixture.cpp:272:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < up.size(); i++)
                     ~~^~~~~~~~~~~
Mixture.cpp:277:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < p.size(); i++)
                     ~~^~~~~~~~~~
Mixture.cpp: In function 'int main()':
Mixture.cpp:335:43: warning: format '%llu' expects argument of type 'long long unsigned int*', but argument 2 has type '__int128*' [-Wformat=]
     scanf("%llu%llu%llu", &Z.z, &Y.z, &X.z);
                           ~~~~            ^
Mixture.cpp:335:43: warning: format '%llu' expects argument of type 'long long unsigned int*', but argument 3 has type '__int128*' [-Wformat=]
Mixture.cpp:335:43: warning: format '%llu' expects argument of type 'long long unsigned int*', but argument 4 has type '__int128*' [-Wformat=]
Mixture.cpp:348:51: warning: format '%llu' expects argument of type 'long long unsigned int*', but argument 2 has type '__int128*' [-Wformat=]
             scanf("%llu%llu%llu", &z.z, &y.z, &x.z);
                                   ~~~~            ^
Mixture.cpp:348:51: warning: format '%llu' expects argument of type 'long long unsigned int*', but argument 3 has type '__int128*' [-Wformat=]
Mixture.cpp:348:51: warning: format '%llu' expects argument of type 'long long unsigned int*', but argument 4 has type '__int128*' [-Wformat=]
Mixture.cpp:335:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%llu%llu%llu", &Z.z, &Y.z, &X.z);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Mixture.cpp:348:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%llu%llu%llu", &z.z, &y.z, &x.z);
             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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