oj.uz

Submission #668089

# Submission time Handle Problem Language Result Execution time Memory
668089 2022-12-02T18:13:32 Z 600Mihnea Tram (CEOI13_tram) C++17
25 / 100
 1000 ms 804 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;

void addPair(int r1, int r2)
{
  perechiDeRanduriInteresanteConsecutive.insert({r1, r2});
}

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));
  randuriInteresante.erase(r);

  assert((int) randuriInteresante.size() >= 2);

  /// optimize here:

  perechiDeRanduriInteresanteConsecutive.clear();
  int last = -1;
  for (auto &r : randuriInteresante)
  {
    if (last != -1)
    {
      perechiDeRanduriInteresanteConsecutive.insert({last, r});
    }
    last = 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);
}

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

}

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

void bagaCePoti(int iq)
{
  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 65 ms 460 KB Output is correct
2 Correct 1 ms 212 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 360 KB Output is correct
2 Correct 1 ms 212 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1084 ms 480 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1092 ms 464 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1085 ms 680 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1084 ms 740 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1073 ms 384 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1075 ms 804 KB Time limit exceeded
2 Halted 0 ms 0 KB -