Submission #440970

#	Time	Username	Problem	Language	Result	Execution time	Memory
440970		prvocislo	Seats (IOI18_seats)	C++17	0 / 100	316 ms	48184 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 5;
int r[maxn], c[maxn], num[maxn], val[maxn*2], cnt[maxn*2], lazy[maxn*2], nr, nc, n;
void build(int l, int r, int vr = 0)
{
  cnt[vr] = r-l+1;
  if (l == r) return;
  build(l, (l+r)/2, vr*2+1), build((l+r)/2+1, r, vr*2+2);
}
void update(int li, int ri, int v, int l, int r, int vr = 0)
{
  if (ri < l || r < li) return;
  if (li <= l && r <= ri)
  {
    val[vr] += v, lazy[vr] += v;
    return;
  }
  update(li, ri, v, l, (l+r)/2, vr*2+1), update(li, ri, v, (l+r)/2+1, r, vr*2+2);
  val[vr] = min(val[vr*2+1], val[vr*2+2]), cnt[vr] = 0;
  if (val[vr] == val[vr*2+1]) cnt[vr] += cnt[vr*2+1];
  if (val[vr] == val[vr*2+2]) cnt[vr] += cnt[vr*2+2];
  val[vr] += lazy[vr];
}
int id(int x, int y)
{
  if (x < 0 || y < 0 || x >= nr || y >= nc) return nr*nc;
  return nc*x + y;
}
void change2x2(int x, int y, int d)
{
  array<int, 4> a;
  for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) a[i*2+j] = num[id(x+i, y+j)];
  sort(a.begin(), a.end());
  for (int i = 0; i < 2; i++) if (a[i*2] < a[i*2+1]) update(a[i*2], a[i*2+1]-1, d, 0, n-1);
}
void change(int x, int y, int v)
{
  for (int i = -1; i < 1; i++) for (int j = -1; j < 1; j++) change2x2(x+i, y+j, -1);
  num[x*nc+y] = v;
  for (int i = -1; i < 1; i++) for (int j = -1; j < 1; j++) change2x2(x+i, y+j, 1);
}
void give_initial_chart(int NR, int NC, vector<int> R, vector<int> C) {
  nr = NR, nc = NC, n = nr * nc;
  for (int i = 0; i < n; i++)
  {
    r[i] = R[i], c[i] = C[i];
    num[r[i]*nc+c[i]] = i;
  } num[nr*nc] = n;
  for (int i = -1; i < nr; i++) for (int j = -1; j < nc; j++) change2x2(i, j, 1);
  build(0, n-1);
}
int swap_seats(int a, int b) {
  change(r[a], c[a], b);
  change(r[b], c[b], a);
  swap(r[a], r[b]), swap(c[a], c[b]);
  return cnt[0];
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 6
• Subtask 3: 0 / 20
• Subtask 4: 0 / 6
• Subtask 5: 0 / 33
• Subtask 6: 0 / 30