Submission #668103

#	Time	Username	Problem	Language	Result	Execution time	Memory
668103		600Mihnea	Tram (CEOI13_tram)	C++17	0 / 100	245 ms	32144 KiB

tram

#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);
  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);
  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;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 15
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 15
• Subtask 8: 0 / 20