#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 150000 + 7;
const ll INF = (ll) 1e18 + 7;
int n;
int cnt_active;
bool is_active[N][2];
int rsol[N];
int csol[N];
set<int> randuriInteresantePeColoana[2];
set<int> randuriInteresante;
set<pair<int, int>> perechiDeRanduriInteresanteConsecutive;
vector<int> inds[N];
int curt;
ll computeDist(int r, int c)
{
assert(1 <= r && r <= n);
assert(0 <= c && c <= 1);
/// assert(cnt_active >= 1);
ll sol = INF;
for (int inv = 0; inv <= 1; inv++)
{
auto it = randuriInteresantePeColoana[c ^ inv].lower_bound(r);
if (it != randuriInteresantePeColoana[c ^ inv].end())
{
sol = min(sol, 1LL * (*it - r) * (*it - r) + inv);
}
if (it != randuriInteresantePeColoana[c ^ inv].begin())
{
it--;
sol = min(sol, 1LL * (*it - r) * (*it - r) + inv);
}
}
return sol;
}
priority_queue<array<ll, 3>> pq;
void addPair(int r1, int r2)
{
perechiDeRanduriInteresanteConsecutive.insert({r1, r2});
pair<int, int> it = {r1, r2};
set<pair<int, int>> guys;
guys.insert({it.first, 0});
guys.insert({it.first, 1});
guys.insert({it.second, 0});
guys.insert({it.second, 1});
guys.insert({(it.first + it.second) / 2, 0});
guys.insert({(it.first + it.second) / 2, 1});
guys.insert({(it.first + it.second + 1) / 2, 0});
guys.insert({(it.first + it.second + 1) / 2, 1});
/// cout << " \t\t\t\t\t\t\t\t insert " << r1 << " " << r2 << "\n";
for (auto &guy : guys)
{
int r = guy.first, c = guy.second;
pq.push({computeDist(r, c), -r, -c});
}
}
void delPair(int r1, int r2)
{
assert(perechiDeRanduriInteresanteConsecutive.count({r1, r2}));
perechiDeRanduriInteresanteConsecutive.erase({r1, r2});
}
void add_row(int r)
{
assert(1 <= r && r <= n);
if (randuriInteresante.count(r))
{
return;
}
randuriInteresante.insert(r);
assert((int) randuriInteresante.size() >= 2);
/// optimize here:
{
auto it = randuriInteresante.find(r);
int r1, r2;
assert(it != randuriInteresante.end());
it++;
assert(it != randuriInteresante.end());
r2 = *it;
it--;
assert(it != randuriInteresante.begin());
it--;
r1 = *it;
delPair(r1, r2);
addPair(r1, r);
addPair(r, r2);
}
}
void del_row(int r)
{
assert(1 <= r && r <= n);
if (r == 1 || r == n)
{
return;
}
assert(randuriInteresante.count(r));
assert((int) randuriInteresante.size() >= 2);
/// optimize here:
{
auto it = randuriInteresante.find(r);
int r1, r2;
assert(it != randuriInteresante.end());
it++;
assert(it != randuriInteresante.end());
r2 = *it;
it--;
assert(it != randuriInteresante.begin());
it--;
r1 = *it;
addPair(r1, r2);
delPair(r1, r);
delPair(r, r2);
}
randuriInteresante.erase(r);
}
void add(int r, int c)
{
assert(1 <= r && r <= n);
assert(0 <= c && c <= 1);
assert(is_active[r][c] == 0);
assert(!randuriInteresantePeColoana[c].count(r));
is_active[r][c] = 1;
cnt_active++;
randuriInteresantePeColoana[c].insert(r);
add_row(r);
auto it = randuriInteresante.find(r);
assert(it != randuriInteresante.end());
it++;
if (it != randuriInteresante.end())
{
addPair(r, *it);
}
it--;
if (it != randuriInteresante.begin())
{
it--;
addPair(*it, r);
}
}
void del(int r, int c)
{
assert(1 <= r && r <= n);
assert(0 <= c && c <= 1);
assert(cnt_active >= 1);
assert(is_active[r][c] == 1);
assert(randuriInteresante.count(r));
assert(randuriInteresantePeColoana[c].count(r));
is_active[r][c] = 0;
cnt_active--;
randuriInteresantePeColoana[c].erase(r);
auto it = randuriInteresante.find(r);
assert(it != randuriInteresante.end());
it++;
if (it != randuriInteresante.end())
{
addPair(r, *it);
}
it--;
if (it != randuriInteresante.begin())
{
it--;
addPair(*it, r);
}
if (!randuriInteresantePeColoana[c ^ 1].count(r))
{
del_row(r);
}
}
void bagaCePoti(int iq)
{
while (!pq.empty())
{
ll d = pq.top()[0];
int r = -pq.top()[1];
int c = -pq.top()[2];
/// cout << " = " << d << " | " << r << " " << c << "\n";
pq.pop();
if (computeDist(r, c) != d)
{
continue;
}
rsol[iq] = r;
csol[iq] = c;
return;
}
assert(0);
return;
if (cnt_active == 0)
{
rsol[iq] = 1;
csol[iq] = 0;
return;
}
assert(cnt_active >= 1);
ll bg = 0;
set<pair<int, int>> guys;
for (auto &it : perechiDeRanduriInteresanteConsecutive)
{
guys.insert({it.first, 0});
guys.insert({it.first, 1});
guys.insert({it.second, 0});
guys.insert({it.second, 1});
guys.insert({(it.first + it.second) / 2, 0});
guys.insert({(it.first + it.second) / 2, 1});
guys.insert({(it.first + it.second + 1) / 2, 0});
guys.insert({(it.first + it.second + 1) / 2, 1});
for (auto &p : guys)
{
bg = max(bg, computeDist(p.first, p.second));
}
}
for (auto &p : guys)
{
if (bg == computeDist(p.first, p.second))
{
rsol[iq] = p.first;
csol[iq] = p.second;
return;
}
}
assert(0);
}
int main()
{
#ifdef ONPC
freopen ("input.txt", "r", stdin);
#endif // ONPC
#ifndef ONPC
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#endif // ONPC
int q;
cin >> n >> q;
if (n == 1)
{
cout << "fuck this special case\n";
exit(0);
}
randuriInteresante.insert(1);
randuriInteresante.insert(n);
addPair(1, n);
for (int iq = 1; iq <= q; iq++)
{
string s;
cin >> s;
assert(s == "E" || s == "L");
if (s == "E")
{
bagaCePoti(iq);
cout << rsol[iq] << " " << csol[iq] + 1 << "\n";
add(rsol[iq], csol[iq]);
continue;
}
assert(s == "L");
int pos;
cin >> pos;
del(rsol[pos], csol[pos]);
}
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
3928 KB |
Output is correct |
| 2 |
Correct |
2 ms |
3924 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
3924 KB |
Output is correct |
| 2 |
Correct |
3 ms |
3796 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
11 ms |
4716 KB |
Output is correct |
| 2 |
Correct |
9 ms |
4324 KB |
Output is correct |
| 3 |
Correct |
13 ms |
4692 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
11 ms |
4760 KB |
Output is correct |
| 2 |
Correct |
10 ms |
4392 KB |
Output is correct |
| 3 |
Correct |
10 ms |
4712 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
14 ms |
5864 KB |
Output is correct |
| 2 |
Correct |
9 ms |
4344 KB |
Output is correct |
| 3 |
Correct |
12 ms |
5076 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
15 ms |
5864 KB |
Output is correct |
| 2 |
Correct |
10 ms |
4324 KB |
Output is correct |
| 3 |
Correct |
10 ms |
5092 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
195 ms |
12616 KB |
Output is correct |
| 2 |
Correct |
172 ms |
10448 KB |
Output is correct |
| 3 |
Correct |
217 ms |
17244 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
248 ms |
32168 KB |
Output is correct |
| 2 |
Correct |
159 ms |
10612 KB |
Output is correct |
| 3 |
Correct |
236 ms |
17444 KB |
Output is correct |
