oj.uz

Submission #771543

# Submission time Handle Problem Language Result Execution time Memory
771543 2023-07-03T06:15:25 Z myrcella Tram (CEOI13_tram) C++17
100 / 100
 104 ms 21476 KB 
// by szh
#include<bits/stdc++.h>
using namespace std;

typedef long long LL;

#define int LL
#define F first
#define S second
#define pii pair<LL, LL>
#define pb push_back
#define debug(x) cerr << #x << "=" << x << endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a; i < (b); i++)
#define MP make_pair
#define SZ(x) (static_cast<int>(x.size()))
#define MOD 1000000007
#define ALL(x) x.begin(), x.end()
void inc(int &a, int b) {a = (a+b)%MOD;}
void dec(int &a, int b) {a = (a-b+MOD)%MOD;}
int prod(int a,int b) {return LL(a)*LL(b)%MOD;}
int lowbit(int x) {return x&(-x);}

const int maxn = 3e5;

int n, m;

set <int> pos;
set <pair<int, pii> > emptyp;
bool mark[maxn][2];
set <pii> cell;
vector <pii> res;

pair<int, pii> fakegetmn(int le, int re) {
  if (le == -1 and re == maxn) {
	return {1e18, {0, 0}};
  }
  if (le == -1) {
	int tmp = re;
	int op = 0;
	if (mark[re][0] and !mark[re][1]) op = 1;
	tmp *= tmp;
	tmp += (!mark[re][0] or !mark[re][1]);
	return {tmp, {0, op}};
  }
  if (re == maxn) {
	int tmp = n - 1 - le;
	int op = 0;
	if (mark[le][0] and !mark[le][1]) op = 1;
	return {tmp * tmp + (!mark[le][0] or !mark[le][1]), {n - 1, op}};
  }
  int tmp = (re - le) /2;
  if (tmp * 2 == re - le) {
	if (!mark[le][0] and !mark[re][0])
	  return {tmp * tmp + 1, {le + tmp, 0}};
	if (!mark[le][1] and !mark[re][1])
	  return {tmp * tmp + 1, {le + tmp, 1}};
	return {tmp * tmp, {le + tmp, 0}};
  }
  int tmpp = tmp;
  tmp *= tmp;
  tmp++;
  pii ret;
  if (!mark[le][0]) ret.F = tmpp + le, ret.S = 0;
  else if (!mark[le][1]) ret.F = tmpp + le, ret.S = 1;
  else if (!mark[re][0]) ret.F = re - tmpp, ret.S = 0;
  else if (!mark[re][1]) ret.F = re - tmpp, ret.S = 1;
  else ret.F = tmpp + le, ret.S = 0, tmp--;
  
  return {tmp, ret};
}

pair<int, pii> getmn(int l, int r) {
  auto x = fakegetmn(l, r);
  x.F = -x.F;
  if (x.F == -2 and x.S.F == 1 and x.S.S == 0) debug(l), debug(r);
  //debug(x.F);
  return x;
}

void bye(int x) {
  //cout << "bye\n";
  pos.erase(x);
  auto it = pos.lower_bound(x);
  int r = maxn;
  if (it != pos.end()) r = (*it);
  int l = -1;
  if (it != pos.begin()) l = (*(--it));
  //debug(l), debug(r);
  if (l != -1 or x != 0) emptyp.erase(getmn(l, x));
  if (x != n - 1 or r != maxn) emptyp.erase(getmn(x, r));
  if (l == -1 and r == 0) return;
  if (l == n - 1 and r == maxn) return;
  emptyp.insert(getmn(l, r));
}

void hi(int x) {
  //cout << "hi\n";
  auto it = pos.lower_bound(x);
  int r = maxn;
  if (it != pos.end()) r = (*it);
  int l = -1;
  if (it != pos.begin()) l = (*(--it));
  if (l == -1 and r == 0);
  else if (l == n - 1 and r == maxn);
  else {
	
	emptyp.erase(getmn(l, r));
	
  }
  if (l != -1 or x != 0) {
	//debug(getmn(l, x).S.F);
	emptyp.insert(getmn(l, x));
  }
  if (x != n - 1 or r != maxn) {
	emptyp.insert(getmn(x, r));
	//debug(getmn(x, r).S.F);
  }
  pos.insert(x);
  /*for (auto it : emptyp) {
	cout << it.F << " " << it.S.F << " " << it.S.S << endl;
  }*/
}

void addppl() {
  if (pos.empty()) {
	emptyp.insert({-1e18, {0LL, 0LL}});
  }
  assert(!emptyp.empty());
  pii ans = (*emptyp.begin()).S;
  
  //debug((*emptyp.begin()).F);
  if ((*emptyp.begin()).F == -1) {
	ans = (*cell.begin());
	//debug(233);
  }
  else emptyp.erase(emptyp.begin());
  cell.erase(ans);
  if (mark[ans.F][ans.S ^1]) bye(ans.F);
  mark[ans.F][ans.S] = 1;
  hi(ans.F);
  cout << ans.F + 1 << ' ' << ans.S + 1 << '\n';
  res.pb(ans);
  return;
}

signed main() {
  // freopen("input.txt","r",stdin);
  std::ios::sync_with_stdio(false); cin.tie(0);
  cin >> n >> m;
  rep(i, 0, n) cell.insert({i, 0}), cell.insert({i, 1});
  
  while (m--) {
	//cout << "-------\n";
	char c;
	cin >> c;
	if (c == 'E') addppl();
	else {
	  int id; cin >> id;
	  id--;
	  pii ans = res[id];
	  assert(ans.F != -1);
	  cell.insert(ans);
	  //erase ans.F first
	  bye(ans.F);
	  mark[ans.F][ans.S] = 0;
	  //debug(ans.F), debug(ans.S);
	  if (mark[ans.F][ans.S ^ 1]) hi(ans.F);
	  res.pb({-1, -1});
	}
  }
  return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
15.0 / 15.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 628 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 560 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 19472 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 62 ms 19500 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 19500 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 57 ms 19384 KB Output is correct

Subtask #7
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 3392 KB Output is correct
2 Correct 26 ms 1268 KB Output is correct
3 Correct 31 ms 3244 KB Output is correct

Subtask #8
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 21476 KB Output is correct
2 Correct 23 ms 1308 KB Output is correct
3 Correct 86 ms 20440 KB Output is correct