oj.uz

Submission #255171

# Submission time Handle Problem Language Result Execution time Memory
255171 2020-07-31T13:30:55 Z davitmarg Mixture (BOI20_mixture) C++17
0 / 100
 1 ms 384 KB 
/*
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=acos(-1),eps=10e-7;
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);
    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;
    bool inv = 0;

    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.lower_bound(e-eps);
    e = *it;

    LD lst, nxt;
    bool inv = 0;

    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(abs(e - lst) - eps));
    mx.erase(mx.lower_bound(abs(e - nxt) - 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 >> X >> Y >> Z;
    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 >> x >> y >> z;
            x /= z;
            y /= z;
            x -= X;
            y -= Y;
            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;
}

/*

0 0 1
4
A 1 1 1
A -1 1 1
A 0 -1 1
A -1 -1 1

*/

Compilation message

Mixture.cpp: In function 'void add(long double)':
Mixture.cpp:70:10: warning: unused variable 'inv' [-Wunused-variable]
     bool inv = 0;
          ^~~
Mixture.cpp: In function 'void rem(long double)':
Mixture.cpp:113:10: warning: unused variable 'inv' [-Wunused-variable]
     bool inv = 0;
          ^~~

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Incorrect 0 ms 384 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Incorrect 0 ms 384 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Incorrect 0 ms 384 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Incorrect 0 ms 384 KB Output isn't correct
7 Halted 0 ms 0 KB -