Submission #255146

#TimeUsernameProblemLanguageResultExecution timeMemory
255146davitmargMixture (BOI20_mixture)C++17
0 / 100
3 ms640 KiB
/* 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-5; 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.find(abs(e - lst) - eps)); mx.erase(mx.find(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)); 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))); 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; 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 - 1], vy[p - 1]); } 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 (stderr)

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;
          ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...