oj.uz

Submission #668104

# Submission time Handle Problem Language Result Execution time Memory
668104 2022-12-02T18:32:37 Z 600Mihnea Tram (CEOI13_tram) C++17
100 / 100
 248 ms 32168 KB 
#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;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3928 KB Output is correct
2 Correct 2 ms 3924 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3924 KB Output is correct
2 Correct 3 ms 3796 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory 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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory 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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory 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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory 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

Subtask #7
15.0 / 15.0

# Verdict Execution time Memory 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

Subtask #8
20.0 / 20.0

# Verdict Execution time Memory 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