#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;
vector<wsp> vec;
vector<pair<pair<ll, ll>, int>> pom[6];
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) {
// cout << p.st << " " << p.nd << '\n';
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) {
if (ile[p] == 1) {
if (ile[{-p.st, -p.nd}] >= 1) {
pol--;
}
}
ile[p]--;
if (pol > 0) {
return true;
}
return false;
}
bool spr1() {
if (ile[{0, 0}] > 0) {
return true;
}
return false;
}
void wypisz(pair<ll, ll> p) {
cout << p.st << " " << p.nd << " ";
}
pair<ll, ll> przemien(wsp p) {
ll x = p.st.st;
ll y = p.st.nd;
ll z = p.nd;
// cout << "x = " << x << " y = " << y << " z = " << z << '\n';
ll X = x * c - a * z;
ll Y = y * c - b * z;
// if (z == 0 || Y == 0) {
// cout << "XDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD" << '\n';
// }
if (z == 0) {
X = x;
Y = y;
}
ll d = __gcd(abs(X), abs(Y));
if (d != 0) {
X /= d;
Y /= d;
}
// cout << "X = " << X << " Y = " << Y << '\n';
return {X, Y};
}
int zmiana(pair<ll, ll> p) {
if (p.nd == 0) {
if (p.st < 0) {
return 2;
}
return 5;
}
if (p.nd < 0) {
if (p.st < 0) {
return 1;
}
return 0;
}
if (p.st > 0) {
return 4;
}
return 3;
}
void wyp(__int128_t x) {
vector<char> vec;
// if (x == 0) {
// cout << "BRRRRUUUUUUUUUUUUUUUUUHHHHHHHHH" << '\n';
// return ;
// }
while (x > 0) {
int t = (x % 10);
char c = t + '0';
vec.pb(c);
x /= 10;
}
reverse(vec.begin(), vec.end());
for (auto c: vec) {
cout << c;
}
cout << '\n';
}
bool por(pair<pair<ll, ll>, int> x2, pair<pair<ll, ll>, int> y2) {
pair<ll, ll> x = x2.st;
pair<ll, ll> y = y2.st;
if (x2 == y2) return false;
if (zmiana(x) == zmiana(y)) {
// cout << "TUuuuuuuuuu = " << x.st << " " << x.nd << " " << y.st << " " << y.nd << '\n';
bool zmien = true;
if (x.st < 0 && x.nd > 0) {
zmien = false;
}
else if (x.st > 0 && x.nd < 0) {
zmien = false;
}
__int128_t a = abs(x.st);
__int128_t b = abs(x.nd);
__int128_t c = abs(y.st);
__int128_t d = abs(y.nd);
__int128_t w1 = a * d;
__int128_t w2 = b * c;
// wyp(w1);
// wyp(w2);
if (zmien) {
return (w1 > w2);
}
return (w1 < w2);
}
return zmiana(x) > zmiana(y);
}
void przesort() {
int sz = vec.size();
// cout << "szzzzzzzzzzzzzzzzz = " << sz << '\n';
rep(i, sz) {
pom[zmiana(przemien(vec[i]))].pb({przemien(vec[i]), i});
}
for (int c2 = 5; c2 >= 0; c2--) {
sort(pom[c2].begin(), pom[c2].end(), por);
}
int kt = 1;
// cout << "SORT" << '\n';
for (int c2 = 5; c2 >= 0; c2--) {
for (auto p: pom[c2]) {
jaki[p.nd] = kt;
// cout << "kt = " << kt << " ";
// pair<ll, ll> paraa = przemien(T[p.nd]);
// wypisz(paraa);
// cout << '\n';
// ld a = paraa.st;
// ld b = paraa.nd;
// ld c = a/b;
// cout << zmiana(paraa) << '\n';
// cout << c << '\n';
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)) {
// cout << "ODEEEEJM = ";
// wypisz(plast);
// wypisz(pnxt);
// cout << '\n';
lic--;
}
if (czytak(plast, pter) || (plast == pter && nrlast >= nr)) {
// cout << "DZIAAAALAAAA = ";
// wypisz(plast);
// wypisz(pter);
// cout << '\n';
lic++;
}
if (czytak(pter, pnxt) || (pter == pnxt && nr >= nrnxt)) {
// cout << "DZIAAAALAAAA = ";
// wypisz(pter);
// wypisz(pnxt);
// cout << '\n';
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);
cout << fixed << setprecision(10);
cin >> a >> b >> c;
int liccccc = 0;
while (c == 0) {
liccccc++;
swap(a, c);
swap(b, c);
}
ll nwdd = __gcd(a, __gcd(b, c));
a /= nwdd;
b /= nwdd;
c /= nwdd;
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;
// cout << "x = " << x << " y = " << y << " z = " << z << '\n';
rep(cos, liccccc) {
swap(x, z);
swap(y, z);
}
nwdd = __gcd(x, __gcd(y, z));
x /= nwdd;
y /= nwdd;
z /= nwdd;
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;
}
// cout << "ZIIUUUUUUUUUUUUUUUUUUUUUUUUUUUUMMM lic = " << lic << '\n';
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... |