Submission #278680

#	Time	Username	Problem	Language	Result	Execution time	Memory
278680		ASDF123	Seats (IOI18_seats)	C++14	11 / 100	4085 ms	161052 KiB

seats

//#include "seats.h"
#include <bits/stdc++.h>
#define chkmax(a, b) a = max(a, (b))
#define chkmin(a, b) a = min(a, (b))
#define szof(s) (int)s.size()
#define pii pair<int, int>
#define fr first
#define sc second
#define y1 asdafsafasfsa
using namespace std;


const int INF = 0x3f3f3f3f;
const int N = 1e6 + 5;
int r[N], c[N];
int ourH, ourW;
int S;
int color[N], cnt = 1;

struct node {
  int mn, mx;
  node() {
    mn = INF;
    mx = -INF;
  }
};

bool after = false;

struct Tree {
  vector <node> tree;
  Tree() {
  }
  void init(int n) {
    tree.resize(n * 4);
  }
  void upd(int pos, int val, int v, int tl, int tr) {
    if (tl == tr) {
      tree[v].mn = tree[v].mx = val;
      return;
    }
    int mid = tl + tr >> 1;
    if (pos <= mid) {
      upd(pos, val, v + v, tl, mid);
    }
    else {
      upd(pos, val, v + v + 1, mid + 1, tr);
    }
    tree[v].mn = min(tree[v + v].mn, tree[v + v + 1].mn);
    tree[v].mx = max(tree[v + v].mx, tree[v + v + 1].mx);
  }
  pii merge(pii a, pii b) {
    return { min(a.fr, b.fr), max(a.sc, b.sc) };
  }
  pii getpair(int l, int r, int v, int tl, int tr) {
    if (l <= tl && tr <= r) {
      return { tree[v].mn, tree[v].mx };
    }
    if (l > tr || tl > r) {
      return { INF, -INF };
    }
    int mid = tl + tr >> 1;
    return merge(getpair(l, r, v + v, tl, mid), getpair(l, r, v + v + 1, mid + 1, tr));
  }
  int get(int l, int r, int type, int v, int tl, int tr) {
    if (l <= tl && tr <= r) {
      if (type == 1) {
        return tree[v].mn;
      }
      else {
        return tree[v].mx;
      }
    }
    if (l > tr || tl > r) {
      if (type == 1) {
        return INF;
      }
      else {
        return -INF;
      }
    }
    int mid = tl + tr >> 1;
    int lft = get(l, r, type, v + v, tl, mid);
    int rgt = get(l, r, type, v + v + 1, mid + 1, tr);
    if (type == 1) {
      return min(lft, rgt);
    }
    else {
      return max(lft, rgt);
    }
  }
} rows, columns;
Tree row[1005];
Tree col[1005];


void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
  for (int i = 0; i < H * W; i++) {
    r[i + 1] = R[i] + 1;
    c[i + 1] = C[i] + 1;
  }
  ourH = H;
  ourW = W;
  S = ourH * ourW;
  rows.init(S);
  columns.init(S);
  for (int i = 1; i <= S; i++) {
    rows.upd(i, r[i], 1, 1, S);
    columns.upd(i, c[i], 1, 1, S);
  }
  if (ourH <= 1000 && ourW <= 1000) {
    for (int i = 1; i <= ourH; i++) {
      row[i].init(ourW);
    }
    for (int i = 1; i <= ourW; i++) {
      col[i].init(ourH);
    }
    for (int i = 1; i <= ourH * ourW; i++) {
      row[r[i]].upd(c[i], i, 1, 1, ourW);
      col[c[i]].upd(r[i], i, 1, 1, ourH);
    }
  }
  //show();
}

int subtask12(int a, int b) {
  int ans = 0;
  a++, b++;
  swap(r[a], r[b]);
  swap(c[a], c[b]);
  node R, C;
  for (int i = 1; i <= S; i++) {
    chkmin(R.mn, r[i]);
    chkmax(R.mx, r[i]);
    chkmin(C.mn, c[i]);
    chkmax(C.mx, c[i]);
    if ((R.mx - R.mn + 1) * (C.mx - C.mn + 1) == i) {
      ans++;
    }
  }
  return ans;
}

int square(int pos) {
  pii a = rows.getpair(1, pos, 1, 1, S);
  pii b = columns.getpair(1, pos, 1, 1, S);
  return (a.sc - a.fr + 1) * (b.sc - b.fr + 1);
}

int get(int pos) {
  int s = square(pos);
  pii a = rows.getpair(1, s, 1, 1, S);
  pii b = columns.getpair(1, s, 1, 1, S);
  int ss = square(s);
  return ss == s ? ss : -1;
}

int subtask3(int a, int b) {
  cnt++;
  a++, b++;
  int ans = 0;
  row[r[a]].upd(c[a], b, 1, 1, ourW);
  col[c[a]].upd(r[a], b, 1, 1, ourH);
  row[r[b]].upd(c[b], a, 1, 1, ourW);
  col[c[b]].upd(r[b], a, 1, 1, ourH);
  swap(r[a], r[b]);
  swap(c[a], c[b]);
  rows.upd(a, r[a], 1, 1, S);
  columns.upd(a, c[a], 1, 1, S);
  rows.upd(b, r[b], 1, 1, S);
  columns.upd(b, c[b], 1, 1, S);
  for (int i = 1; i <= ourH; i++) {
    int best = row[i].get(1, ourW, 1, 1, 1, ourW);
    int x = get(best);
    if (x != -1) {
      if (color[x] != cnt) {
        ans++;
      }
      color[x] = cnt;
    }
  }
  for (int i = 1; i <= ourW; i++) {
    int best = col[i].get(1, ourH, 1, 1, 1, ourH);
    int x = get(best);
    if (x != -1) {
      if (color[x] != cnt) {
        ans++;
      }
      color[x] = cnt;
    }
  }
  return ans;
}

int swap_seats(int a, int b) {
  if (ourH * ourW <= 10000) {
    return subtask12(a, b);
  }
  if (ourH <= 1000 && ourW <= 1000) {
    return subtask3(a, b);
  }
  assert(false);
}

Compilation message (stderr)

seats.cpp: In member function 'void Tree::upd(int, int, int, int, int)':
seats.cpp:42:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |     int mid = tl + tr >> 1;
      |               ~~~^~~~
seats.cpp: In member function 'std::pair<int, int> Tree::getpair(int, int, int, int, int)':
seats.cpp:62:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   62 |     int mid = tl + tr >> 1;
      |               ~~~^~~~
seats.cpp: In member function 'int Tree::get(int, int, int, int, int, int)':
seats.cpp:82:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   82 |     int mid = tl + tr >> 1;
      |               ~~~^~~~
seats.cpp: In function 'int get(int)':
seats.cpp:152:7: warning: variable 'a' set but not used [-Wunused-but-set-variable]
  152 |   pii a = rows.getpair(1, s, 1, 1, S);
      |       ^
seats.cpp:153:7: warning: variable 'b' set but not used [-Wunused-but-set-variable]
  153 |   pii b = columns.getpair(1, s, 1, 1, S);
      |       ^

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