#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2")
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 150001;
int n, m;
multiset<array<int, 3>> pq;
vector<array<int, 2>> lol;
map<int, int> what;
template<class OwO, class It>
void P(It l, It r, OwO uwu) {
if(++l == what.begin() && r == what.end()) return;
--l;
if(r == what.begin()) {
//cout << "This\n";
l = what.end();
if(r->first == 1) {
if(r->second == 1) uwu(l, r, {1, 2});
if(r->second == 2) uwu(l, r, {1, 1});
} else {
if(r->second == 3) {
uwu(l, r, {1, 1});
uwu(l, r,{1, 2});
}
if(r->second == 1) {
uwu(l, r, {1, 2});
}
if(r->second == 2) {
uwu(l, r, {1, 1});
}
}
if(r->first == 2) {
if(r->second == 1) uwu(l, r, {2, 2});
if(r->second == 2) uwu(l, r, {2, 1});
}
return;
}
if(r == what.end()) {
//cout << "This 2222\n";
if(l->first == n) {
if(l->second == 1) uwu(l, r, {n, 2});
if(l->second == 2) uwu(l, r, {n, 1});
} else {
//cout << n << ":thonkms\n";
if(l->second == 3) {
uwu(l, r, {n, 1});
uwu(l, r, {n, 2});
}
if(l->second == 1) {
uwu(l, r, {n, 2});
}
if(l->second == 2) {
uwu(l, r, {1, 1});
}
}
if(l->first == n-1) {
if(l->second == 1) uwu(l, r, {n-1, 2});
if(l->second == 2) uwu(l, r, {n-1, 1});
}
return;
}
if(l->second+r->second==3) {
if((l->first-r->first)%2) {//even
if(l->first+1 != r->first) {
int mid = (l->first+r->first)/2;
uwu(l, r, {mid , 3^l->second});
uwu(l, r, {mid+1, 3^r->second});
}
} else {//odd
int mid = (l->first+r->first)/2;
uwu(l, r, {mid, 1});
uwu(l, r, {mid, 2});
}
if(r->first-l->first < 3) {
uwu(l, r, {l->first, 3^l->second});
uwu(l, r, {r->first, 3^r->second});
}
return;
}
if(min(l->second, r->second) == 3) {
if(l->first+1 != r->first) {
int mid = (l->first+r->first)/2;
uwu(l, r, {mid, 1});
uwu(l, r, {mid, 2});
}
return;
}
if(max(l->second, r->second) == 3) {
int p = l->second != 3 ? l->first : r->first;
int mn = min(l->second, r->second);
int mid = (l->first+r->first)/2;
if(r->first-l->first > 2) {
if((l->first+r->first)%2) mid += p > mid;
uwu(l, r, {mid, 3^mn});
}
if(r->first-l->first == 2) {
uwu(l, r, {mid, 1});
uwu(l, r, {mid, 2});
}
if(r->first-l->first <= 2) {
uwu(l, r, {p, 3^mn});
}
return;
}
int mid = (l->first+r->first)/2;
int F = 3^(l->second|r->second);
if(l.first+1 != r.first) {
uwu(l, r, {mid, F});
if((l->first+r->first)%2) {
mid++;
uwu(l, r, {mid, F});
}
}
}
template<class It>
void add(It l, It r, array<int, 2> x) {
int d = 1<<30;
assert(x[1] <= 2);
for(auto i : {l, r})
if(i != what.end()) {
int c = 0;
if(i->first == x[0]) c = 2;
else c = abs(i->first-x[0])*2 + abs(i->second-x[1]);
d = min(d, c);
}
pq.insert({d, -x[0], -x[1]});
}
template<class It>
void del(It l, It r, array<int, 2> x) {
int d = 1<<30;
for(auto i : {l, r})
if(i != what.end()) {
int c = 0;
if(i->first == x[0]) c = 2;
else c = abs(i->first-x[0])*2 + abs(i->second-x[1]);
d = min(d, c);
}
pq.erase(pq.find({d, -x[0], -x[1]}));
}
void add() {
int x, y;
if(pq.empty()) x = 1, y = 1, lol.push_back({1, 1});
else {
auto [di, xx, yy] = *pq.rbegin();xx*=-1,yy*=-1;
x = xx, y = yy;
lol.push_back({x, y});
}
what[x] += 0;
auto p = what.find(x);
auto l = p;--l;
auto r = p;++r;
auto DEL = del<decltype(l)>;
auto ADD = add<decltype(l)>;
if(p->second == 0) {
if(what.size() > 1) P(l, r, DEL);
} else P(l, p, DEL), P(p, r, DEL);
what[x] += y;
P(l, p, ADD);
//cout << "this should produce the interesting stuff\n";
P(p, r, ADD);
}
void fuck(int id) {
auto p = what.find(lol[id][0]);
auto l = p;--l;
auto r = p;++r;
auto DEL = del<decltype(l)>;
auto ADD = add<decltype(l)>;
P(l, p, DEL), P(p, r, DEL);
what[lol[id][0]] -= lol[id][1];
if(what[lol[id][0]] == 0) {
what.erase(lol[id][0]);
P(l, r, ADD);
} else P(l, p, ADD), P(p, r, ADD);
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int t;
cin >> n >> m;
char c;
while(m--) {
cin >> c;
if(c == 'E') add(), cout << lol.back()[0] << " " << lol.back()[1] << '\n';
else cin >> t, fuck(t-1), lol.push_back({-1, -1});
continue;
cout << "QUERIES LEFT : " << m << endl;
for(auto [d, x, y] : pq) cout << d << " | " << x << " " << y << " " << endl;
for(auto [x, y] : what) cout << x << " ~ " << y << endl;
}
}
Compilation message
tram.cpp: In instantiation of 'void P(It, It, OwO) [with OwO = void (*)(std::_Rb_tree_iterator<std::pair<const int, int> >, std::_Rb_tree_iterator<std::pair<const int, int> >, std::array<int, 2>); It = std::_Rb_tree_iterator<std::pair<const int, int> >]':
tram.cpp:156:34: required from here
tram.cpp:108:7: error: 'struct std::_Rb_tree_iterator<std::pair<const int, int> >' has no member named 'first'
108 | if(l.first+1 != r.first) {
| ~~^~~~~
tram.cpp:108:20: error: 'struct std::_Rb_tree_iterator<std::pair<const int, int> >' has no member named 'first'
108 | if(l.first+1 != r.first) {
| ~~^~~~~
