#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define st first
#define nd second
#define pb push_back
#define wsp pair<pair<ll, ll>, ll>
const int MAXN = 1e5 + 7;
ld INF = 1e15;
vector<wsp> vec;
vector<pair<pair<ll, ll>, int>> pom;
map <pair<ll, ll>, int> ile;
set<pair<int, int>> S;
map<int, int> jaki;
wsp T[MAXN];
int pol = 0;
int lic = 0;
ll a, b, c;
map<wsp, int> Sile;
bool dod(pair<ll, ll> p) {
ile[p]++;
if (ile[p] == 1) {
if (ile[{-p.st, -p.nd}] >= 1) {
pol++;
}
}
if (pol > 0) {
return true;
}
return false;
}
bool odejm(pair<ll, ll> p) {
ile[p]--;
if (ile[p] == 0) {
if (ile[{-p.st, -p.nd}] >= 1) {
pol--;
}
}
if (pol > 0) {
return true;
}
return false;
}
bool spr1() {
if (ile[{0, 0}] > 0) {
return true;
}
return false;
}
pair<ll, ll> przemien(wsp p) {
ll x = p.st.st;
ll y = p.st.nd;
ll z = p.nd;
ll X = x * c - a * z;
ll Y = y * c - b * z;
ll d = __gcd(abs(X), abs(Y));
if (d != 0) {
X /= d;
Y /= d;
}
return {X, Y};
}
bool por(pair<pair<ll, ll>, int> x2, pair<pair<ll, ll>, int> y2) {
pair<ld, ld> x = x2.st;
pair<ld, ld> y = y2.st;
ld t1 = x.st/x.nd;
if (x.st < 0) {
t1 -= (INF);
}
ld t2 = y.st/y.nd;
if (y.st < 0) {
t2 -= (INF);
}
return (t1 > t2);
}
void przesort() {
int sz = vec.size();
rep(i, sz) {
pom.pb({przemien(vec[i]), i});
}
sort(pom.begin(), pom.end(), por);
int kt = 1;
for (auto p: pom) {
jaki[p.nd] = kt;
kt++;
}
}
bool czytak(pair<ll, ll> p1, pair<ll, ll> p2) {
if ((p1.st * p2.nd - p2.st * p1.nd) > 0) {
return true;
}
return false;
}
bool patrz(wsp p, int kt) {
// cout << "HHH" << endl;
int nr = jaki[kt];
S.insert({nr, kt});
auto it = S.upper_bound({nr, kt});
auto it2 = S.lower_bound({nr, kt});
// cout << "t11" << endl;
if (it2 == S.begin()) {
it2 = S.end();
}
// cout << "PR" << endl;
it2--;
if (it == S.end()) {
it = S.begin();
}
// cout << "XDD" << endl;
int ktlast = (*it2).nd;
int nrlast = (*it2).st;
int ktnxt = (*it).nd;
int nrnxt = (*it).st;
pair<ll, ll> plast = przemien(T[ktlast]);
pair<ll, ll> pnxt = przemien(T[ktnxt]);
pair<ll, ll> pter = przemien(T[kt]);
if (czytak(plast, pnxt) || (plast == pnxt && nrlast >= nrnxt)) {
lic--;
}
if (czytak(plast, pter) || (plast == pter && nrlast >= nr)) {
lic++;
}
if (czytak(pter, pnxt) || (pter == pnxt && nr >= nrnxt)) {
lic++;
}
if (lic == 0) {
return true;
}
return false;
}
bool patrz2(wsp p, int kt) {
int nr = jaki[kt];
// cout << "XD" << endl;
S.erase({nr, kt});
// cout << "XD2" << endl;
if ((int)S.size() == 0) {
lic = 0;
return false;
}
auto it = S.upper_bound({nr, kt});
auto it2 = S.lower_bound({nr, kt});
// cout << "XD3" << endl;
if (it2 == S.begin()) {
it2 = S.end();
}
it2--;
if (it == S.end()) {
it = S.begin();
}
int ktlast = (*it2).nd;
int nrlast = (*it2).st;
int ktnxt = (*it).nd;
int nrnxt = (*it).st;
pair<ll, ll> plast = przemien(T[ktlast]);
pair<ll, ll> pnxt = przemien(T[ktnxt]);
pair<ll, ll> pter = przemien(T[kt]);
if (czytak(plast, pnxt) || (plast == pnxt && nrlast >= nrnxt)) {
lic++;
}
if (czytak(plast, pter) || (plast == pter && nrlast >= nr)) {
lic--;
}
if (czytak(pter, pnxt) || (pter == pnxt && nr >= nrnxt)) {
lic--;
}
if (lic == 0) {
return true;
}
return false;
}
struct upd {
int typ;
ll x, y, z;
};
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> a >> b >> c;
vector<upd> zm;
int q;
cin >> q;
int ktor = 0;
rep(i, q) {
char s;
cin >> s;
if (s == 'A') {
ll x, y, z;
cin >> x >> y >> z;
zm.pb({1, x, y, z});
vec.pb({{x, y}, z});
T[ktor] = {{x, y}, z};
ktor++;
}
else {
int nr;
cin >> nr;
nr--;
zm.pb({2, nr, nr, nr});
}
}
przesort();
// cout << "XD" << endl;
ktor = 0;
rep(i, q) {
upd now = zm[i];
bool c1, c2, c3;
// cout << "i = " << i << endl;
if (now.typ == 1) {
c2 = dod(przemien(T[ktor]));
// cout << "REL" << endl;
c1 = spr1();
// cout << "FR" << endl;
c3 = patrz(T[ktor], ktor);
// cout << "SK" << endl;
ktor++;
}
else {
c2 = odejm(przemien(T[zm[i].x]));
c1 = spr1();
// cout << "FR" << endl;
c3 = patrz2(T[zm[i].x], zm[i].x);
// cout << "SK" << endl;
}
if (c1) {
cout << 1 << '\n';
}
else if (c2) {
cout << 2 << '\n';
}
else if (c3) {
cout << 3 << '\n';
}
else {
cout << 0 << '\n';
}
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |